Factor versus palindromic complexity of uniformly recurrent infinite words
From MaRDI portal
Publication:2373751
DOI10.1016/J.TCS.2007.03.019zbMATH Open1119.68137arXivmath/0603607OpenAlexW2012761039MaRDI QIDQ2373751FDOQ2373751
Peter Baláži, Z. Masáková, Edita Pelantová
Publication date: 16 July 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: We study the relation between the palindromic and factor complexity of infinite words. We show that for uniformly recurrent words one has P(n)+P(n+1) leq Delta C(n) + 2, for all n in N. For a large class of words it is a better estimate of the palindromic complexity in terms of the factor complexity then the one presented by Allouche et al. We provide several examples of infinite words for which our estimate reaches its upper bound. In particular, we derive an explicit prescription for the palindromic complexity of infinite words coding r-interval exchange transformations. If the permutation pi connected with the transformation is given by pi(k)=r+1-k for all k, then there is exactly one palindrome of every even length, and exactly r palindromes of every odd length.
Full work available at URL: https://arxiv.org/abs/math/0603607
Recommendations
- ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
- Palindromic complexity of infinite words associated with non-simple Parry numbers
- A connection between palindromic and factor complexity using return words
- Topological invariants for words of linear factor complexity
- Palindromic complexity of infinite words associated with simple Parry numbers
infinite wordspalindromefactor complexitypalindromic complexityinterval exchange transformationsuniformly recurrent words
Cites Work
- Interval exchange transformations
- Palindrome complexity bounds for primitive substitution sequences
- Palindrome complexity.
- Singular continuous spectrum for palindromic Schrödinger operators
- WHICH DISTRIBUTIONS OF MATTER DIFFRACT ? AN INITIAL INVESTIGATION
- Échanges d'intervalles et transformations induites
- A condition for unique ergodicity of minimal symbolic flows
- Gordon-type arguments in the spectral theory of one-dimensional quasicrystals
- Schroedinger difference equation with deterministic ergodic potentials
- Episturmian words and episturmian morphisms
- Palindromes and Sturmian words
- Palindromic complexity of infinite words associated with simple Parry numbers
- COMBINATORIAL PROPERTIES OF ARNOUX–RAUZY SUBSHIFTS AND APPLICATIONS TO SCHRÖDINGER OPERATORS
- Combinatorial properties of infinite words associated with cut-and-project sequences
- RECENT RESULTS ON EXTENSIONS OF STURMIAN WORDS
- Title not available (Why is that?)
- Complexity of infinite words associated with beta-expansions
Cited In (27)
- Complexity and palindromic defect of infinite words
- On theta-palindromic richness
- On Brlek-Reutenauer conjecture
- On highly potential words
- Weighted prefix normal words: mind the gap
- Pattern avoidance by palindromes
- Infinite words with finite defect
- Palindromic richness
- Upper bound for palindromic and factor complexity of rich words
- Specular sets
- Palindromic complexity of infinite words associated with simple Parry numbers
- A connection between palindromic and factor complexity using return words
- A note on symmetries in the Rauzy graph and factor frequencies
- Sturmian jungle (or garden?) on multiliteral alphabets
- Generalized Thue-Morse words and palindromic richness
- Palindromes in infinite ternary words
- ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
- On the least number of palindromes contained in an infinite word
- Morphic images of episturmian words having finite palindromic defect
- Matrices of 3-iet preserving morphisms
- ALMOST RICH WORDS AS MORPHIC IMAGES OF RICH WORDS
- Introducing privileged words: privileged complexity of Sturmian words
- Languages invariant under more symmetries: overlapping factors versus palindromic richness
- Palindromic richness for languages invariant under more symmetries
- Sturmian and Episturmian Words
- On low-complexity bi-infinite words and their factors
- Palindromic closures using multiple antimorphisms
This page was built for publication: Factor versus palindromic complexity of uniformly recurrent infinite words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2373751)
