Growth rates of complexity of power-free languages
From MaRDI portal
Publication:986556
DOI10.1016/J.TCS.2010.05.017zbMATH Open1196.68121arXiv1009.4415OpenAlexW2080562208MaRDI QIDQ986556FDOQ986556
Authors: Arseny M. Shur 
Publication date: 11 August 2010
Published in: Theoretical Computer Science (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1009.4415
Recommendations
Cites Work
- Title not available (Why is that?)
- Problems in algebraic combinatorics
- Title not available (Why is that?)
- Uniformly growing k-th power-free homomorphisms
- Title not available (Why is that?)
- Automata and forbidden words
- Title not available (Why is that?)
- Combinatorial Complexity of Regular Languages
- On Dejean's conjecture over large alphabets
- Sur un théorème de Thue
- A proof of Dejean’s conjecture
- Last cases of Dejean's conjecture
- Title not available (Why is that?)
- Polynomial versus exponential growth in repetition-free binary words
- The structure of the set of cube-free \(Z\)-words in a two-letter alphabet
- Title not available (Why is that?)
- Repetition-free words
- Enumeration of irreducible binary words
- On the entropy and letter frequencies of ternary square-free words
- Title not available (Why is that?)
- 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
- Title not available (Why is that?)
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
- Avoiding squares over words with lists of size three amongst four symbols
- Branching frequency and Markov entropy of repetition-free languages
- Avoiding or limiting regularities in words
- On the growth rates of complexity of threshold languages
- Growth of power-free languages: numerical and asymptotic bounds
- 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
- On Pnsiot words avoiding 3-repetitions
- Growth of power-free languages over large alphabets
- 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)
