On the growth rates of complexity of threshold languages

DOI10.1051/ita/2010012zbMath1184.68341OpenAlexW2111471998MaRDI QIDQ5190085

Arseny M. Shur, Irina A. Gorbunova

Publication date: 12 March 2010

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_2010__44_1_175_0/

zbMATH Keywords

growth ratecombinatorial complexityDejean's conjecturepower-free languagesthreshold languages

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algebraic theory of languages and automata (68Q70)

Related Items (11)

Branching frequency and Markov entropy of repetition-free languages ⋮ A proof of Dejean’s conjecture ⋮ ON THE EXISTENCE OF MINIMAL β-POWERS ⋮ Growth of power-free languages over large alphabets ⋮ On minimal critical exponent of balanced sequences ⋮ Approaching repetition thresholds via local resampling and entropy compression ⋮ Avoiding or Limiting Regularities in Words ⋮ Growth properties of power-free languages ⋮ The Number of Threshold Words on $n$ Letters Grows Exponentially for Every $n\geq 27$ ⋮ ON PANSIOT WORDS AVOIDING 3-REPETITIONS ⋮ Subword complexity and power avoidance

Cites Work

• A propos d'une conjecture de F. Dejean sur les répétitions dans les mots
• Dejean's conjecture and Sturmian words
• Proof of Dejean's conjecture for alphabets with \(5, 6, 7, 8, 9, 10\) and \(11\) letters
• Uniformly growing k-th power-free homomorphisms
• On Dejean's conjecture over large alphabets
• Sur un théorème de Thue
• A proof of Dejean’s conjecture
• RATIONAL APPROXIMATIONS OF POLYNOMIAL FACTORIAL LANGUAGES
• Combinatorial Complexity of Regular Languages
• Comparing Complexity Functions of a Language and Its Extendable Part
• Dejean's conjecture holds for N ≥ 27
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the growth rates of complexity of threshold languages