Unary Patterns with Permutations

Thue characterized completely the avoidability of unary patterns. Adding function variables gives a general setting capturing avoidance of powers, avoidance of patterns with palindromes, avoidance of powers under coding, and other questions of recent interest. Unary patterns with permutations have been previously analysed only for lengths up to 3. Consider a pattern \(p=\pi _{i_1}(x)\ldots \pi _{i_r}(x)\), with \(r\ge 4\), x a word variable over an alphabet \(\Sigma \) and \(\pi _{i_j}\) function variables, to be replaced by morphic or antimorphic permutations of \(\Sigma \). If \(|\Sigma |\ge 3\), we show the existence of an infinite word avoiding all pattern instances having \(|x|\ge 2\). If \(|\Sigma |=3\) and all \(\pi _{i_j}\) are powers of a single \(\pi \), the length restriction is removed. In general, the restriction on x cannot be removed, even for powers of permutations: for every positive integer n there exists N and a pattern \(\pi ^{i_1}(x)\ldots \pi ^{i_n}(x)\) which is unavoidable over all \(\Sigma \).

Authors and Affiliations

1. Department of Mathematics and Statistics, University of Winnipeg, Winnipeg, Canada

   James Currie

2. Department of Computer Science, Kiel University, Kiel, Germany

   Florin Manea & Dirk Nowotka

Corresponding author

Correspondence to Dirk Nowotka .

Editors and Affiliations

1. University of Liverpool, Liverpool, United Kingdom

   Igor Potapov

Reprints and permissions

© 2015 Springer International Publishing Switzerland

Policies and ethics