Growth rates of complexity of power-free languages

DOI10.1016/J.TCS.2010.05.017MaRDI QIDQ986556zbMATH OpenOpenAlexFDO

Authors 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)

Abstract: We present upper and two-sided bounds of the exponential growth rate for a wide range of power-free languages. All bounds are obtained with the use of algorithms previously developed by the author.

Recommendations

• Growth rates of power-free languages
• Growth of power-free languages: numerical and asymptotic bounds
• Two-Sided Bounds for the Growth Rates of Power-Free Languages
• Combinatorial Complexity of Regular Languages
• Growth of power-free languages over large alphabets

Cites work

• scientific article; zbMATH DE number 6004833 (Why is no real title available?)
• scientific article; zbMATH DE number 6004866 (Why is no real title available?)
• scientific article; zbMATH DE number 3138903 (Why is no real title available?)
• scientific article; zbMATH DE number 5604082 (Why is no real title available?)
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 3912631 (Why is no real title available?)
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 3278338 (Why is no real title available?)
• A proof of Dejean’s conjecture
• Automata and forbidden words
• Combinatorial Complexity of Regular Languages
• Comparing Complexity Functions of a Language and Its Extendable Part
• Enumeration of irreducible binary words
• Last cases of Dejean's conjecture
• On Dejean's conjecture over large alphabets
• On the entropy and letter frequencies of ternary square-free words
• Polynomial versus exponential growth in repetition-free binary words
• Problems in algebraic combinatorics
• Repetition-free words
• Sur un théorème de Thue
• The number of binary cube-free words of length up to 47 and their numerical analysis
• The structure of the set of cube-free \(Z\)-words in a two-letter alphabet
• Uniformly growing k-th power-free homomorphisms

Cited in

(20)

• Two-Sided Bounds for the Growth Rates of Power-Free Languages
• On the existence of minimal \(\beta\)-powers
• Normal forms of random braids.
• On possible growths of Toeplitz languages
• Branching frequency and Markov entropy of repetition-free languages
• Avoiding squares over words with lists of size three amongst four symbols
• Avoiding or limiting regularities in words
• Growth of power-free languages: numerical and asymptotic bounds
• On the growth rates of complexity of threshold languages
• Growth properties of power-free languages
• Growth rates of power-free languages
• Finding the growth rate of a regular or context-free language in polynomial time
• Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time
• Avoiding square-free words on free groups
• Combinatorial Complexity of Regular Languages
• Growth of power-free languages over large alphabets
• On Pnsiot words avoiding 3-repetitions
• Extending Dekking's construction of an infinite binary word avoiding abelian 4-powers
• On Abelian repetition threshold
• Doubled patterns with reversal and square-free doubled patterns

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q986556)