Factor versus palindromic complexity of uniformly recurrent infinite words
From MaRDI portal
Publication:2373751
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.
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
Cites work
- scientific article; zbMATH DE number 5279412 (Why is no real title available?)
- A condition for unique ergodicity of minimal symbolic flows
- COMBINATORIAL PROPERTIES OF ARNOUX–RAUZY SUBSHIFTS AND APPLICATIONS TO SCHRÖDINGER OPERATORS
- Combinatorial properties of infinite words associated with cut-and-project sequences
- Complexity of infinite words associated with beta-expansions
- Episturmian words and episturmian morphisms
- Gordon-type arguments in the spectral theory of one-dimensional quasicrystals
- Interval exchange transformations
- Palindrome complexity bounds for primitive substitution sequences
- Palindrome complexity.
- Palindromes and Sturmian words
- Palindromic complexity of infinite words associated with simple Parry numbers
- RECENT RESULTS ON EXTENSIONS OF STURMIAN WORDS
- Schroedinger difference equation with deterministic ergodic potentials
- Singular continuous spectrum for palindromic Schrödinger operators
- WHICH DISTRIBUTIONS OF MATTER DIFFRACT ? AN INITIAL INVESTIGATION
- Échanges d'intervalles et transformations induites
Cited in
(30)- Complexity and palindromic defect of infinite words
- On theta-palindromic richness
- Palindromic and abelian complexities in binary recurrent words of ultimate complexity \(n + 2\)
- On Brlek-Reutenauer conjecture
- Weighted prefix normal words: mind the gap
- On highly potential words
- Pattern avoidance by palindromes
- Infinite words with finite defect
- Palindromic richness
- Upper bound for palindromic and factor complexity of rich words
- Sturmian jungle (or garden?) On multiliteral alphabets
- 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
- Generalized Thue-Morse words and palindromic richness
- Palindromes in infinite ternary words
- Topological invariants for words of linear factor complexity
- 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
- Factor frequencies in languages invariant under symmetries preserving factor frequencies
- 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
- On low-complexity bi-infinite words and their factors
- Sturmian and Episturmian Words
- 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)
