Growth rates of complexity of power-free languages

DOI10.1016/j.tcs.2010.05.017zbMath1196.68121arXiv1009.4415OpenAlexW2080562208MaRDI QIDQ986556

Arseny M. Shur

Publication date: 11 August 2010

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1009.4415

zbMATH Keywords

growth rateregular languagepower-free languagefinite antidictionary

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (11)

Branching frequency and Markov entropy of repetition-free languages ⋮ ON THE EXISTENCE OF MINIMAL β-POWERS ⋮ On Abelian repetition threshold ⋮ Growth of power-free languages over large alphabets ⋮ Avoiding square-free words on free groups ⋮ Avoiding squares over words with lists of size three amongst four symbols ⋮ Normal forms of random braids. ⋮ Doubled patterns with reversal and square-free doubled patterns ⋮ Avoiding or Limiting Regularities in Words ⋮ Growth properties of power-free languages ⋮ ON PANSIOT WORDS AVOIDING 3-REPETITIONS

Cites Work

• Automata and forbidden words
• Last cases of Dejean's conjecture
• Polynomial versus exponential growth in repetition-free binary words
• Repetition-free words
• Enumeration of irreducible binary words
• Problems in algebraic combinatorics
• Uniformly growing k-th power-free homomorphisms
• On the entropy and letter frequencies of ternary square-free words
• On Dejean's conjecture over large alphabets
• Sur un théorème de Thue
• The structure of the set of cube-free $ Z$-words in a two-letter alphabet
• A proof of Dejean’s conjecture
• Combinatorial Complexity of Regular Languages
• Comparing Complexity Functions of a Language and Its Extendable Part
• The number of binary cube-free words of length up to 47 and their numerical analysis
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Growth rates of complexity of power-free languages