On the growth rates of complexity of threshold languages

DOI10.1051/ita/2010012zbMath1184.68341MaRDI 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 rate; combinatorial complexity; Dejean's conjecture; power-free languages; threshold languages

Mathematics Subject Classification ID

68R15: Combinatorics on words

68Q70: Algebraic theory of languages and automata

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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