Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
429985 | Journal of Computer and System Sciences | 2015 | 13 Pages |
Abstract
We consider a generalisation of the classical problem of pattern avoidance in infinite words with functional dependencies between pattern variables. More precisely, we consider patterns involving permutations. The foremost remarkable fact regarding this new setting is that the notion of avoidability index (the smallest alphabet size for which a pattern is avoidable) is meaningless, since a pattern with permutations that is avoidable in one alphabet can be unavoidable in a larger alphabet. We characterise the (un-)avoidability of all patterns of the form πi(x)πj(x)πk(x)πi(x)πj(x)πk(x), called cubic patterns with permutations here, for all alphabet sizes in both the morphic and antimorphic case.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Florin Manea, Mike Müller, Dirk Nowotka,