Two-Sided Bounds for the Growth Rates of Power-Free Languages

DOI10.1007/978-3-642-02737-6_38zbMath1247.68151OpenAlexW109830933MaRDI QIDQ3637248

Arseny M. Shur

Publication date: 7 July 2009

Published in: Developments in Language Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02737-6_38

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items (15)

Transition Property for $$\alpha $$-Power Free Languages with $$\alpha \ge 2$$ and $$k\ge 3$$ Letters ⋮ Branching frequency and Markov entropy of repetition-free languages ⋮ A ternary square-free sequence avoiding factors equivalent to \(abcacba\) ⋮ Nonrepetitively 3-colorable subdivisions of graphs with a logarithmic number of subdivisions per edge ⋮ Growth of power-free languages over large alphabets ⋮ Growth of power-free languages: numerical and asymptotic bounds ⋮ Avoiding square-free words on free groups ⋮ Avoiding squares over words with lists of size three amongst four symbols ⋮ Construction of a bi-infinite power free word with a given factor and a non-recurrent letter ⋮ Ann wins the nonrepetitive game over four letters and the erase-repetition game over six letters ⋮ On the number of Dejean words over alphabets of 5, 6, 7, 8, 9 and 10 letters ⋮ Growth properties of power-free languages ⋮ Generating square-free words efficiently ⋮ Transition property for cube-free words ⋮ Subword complexity and power avoidance

Cites Work

• Automata and forbidden words
• Polynomial versus exponential growth in repetition-free binary words
• Growth rates of power-free languages
• Repetition-free words
• Uniformly growing k-th power-free homomorphisms
• Exponential lower bounds for the number of words of uniform length avoiding a pattern
• Growth of repetition-free words -- a review
• Combinatorial Complexity of Regular Languages
• Comparing Complexity Functions of a Language and Its Extendable Part
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Two-Sided Bounds for the Growth Rates of Power-Free Languages