Article ID Journal Published Year Pages File Type
429985 Journal of Computer and System Sciences 2015 13 Pages PDF
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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,