Cubic patterns with permutations

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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of computer and system sciences 2015-11, Vol.81 (7), p.1298-1310
Main Authors: Manea, Florin, Müller, Mike, Nowotka, Dirk
Format: Article
Language:English
Subjects:
Avoidable patterns
Combinatorics on words
Permutations
Pseudorepetitions
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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), called cubic patterns with permutations here, for all alphabet sizes in both the morphic and antimorphic case.
ISSN:0022-0000
1090-2724
DOI:10.1016/j.jcss.2015.04.001