Anti-powers in infinite words (Q1747764): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / arXiv ID | |||
Property / arXiv ID: 1606.02868 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4231020 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Anti-power prefixes of the Thue-Morse word / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4075490 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Rainbow generalizations of Ramsey theory: A survey / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4341774 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4529547 / rank | |||
Normal rank |
Latest revision as of 14:32, 15 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Anti-powers in infinite words |
scientific article |
Statements
Anti-powers in infinite words (English)
0 references
27 April 2018
0 references
An anti-power of order \(k\), or a \(k\)-anti-power, is a concatenation of \(k\) consecutive pairwise distinct words of the same length. The authors observe that every infinite word contains powers of any order or anti-powers of any order (Theorem~1). A finitary version of this result is that for all integers \(\ell>1\) and \(k>1\), there exists \(N(\ell,k)\) such that every word of length \(N(\ell,k)\) contains either an \(\ell\)-power or a \(k\)-anti-power (Theorem~14). For \(k>2\), the authors establish the estimates \(k^2-1\leq N(k,k)\leq k^3{k\choose2}\). An infinite word \(w\) is said to avoid \(k\)-anti-powers if no factor of \(w\) is a \(k\)-anti-power. The authors show that an infinite word avoiding \(3\)-anti-powers must be ultimately periodic (Corollary~11) but exhibit an example of an aperiodic word avoiding \(4\)-anti-powers (Proposition~12) and an example of an aperiodic recurrent word avoiding \(6\)-anti-powers (Proposition~13). In contrast, for every aperiodic uniformly recurrent word \(x\) and every \(k>1\), there is an occurrence of a \(k\)-anti-power starting at every position of \(w\) (Corollary~7).
0 references
infinite word
0 references
recurrent word
0 references
uniformly recurrent word
0 references
power
0 references
anti-power
0 references
unavoidable regularity
0 references