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
- 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
- Échanges d'intervalles et transformations induites
- Episturmian words and episturmian morphisms
- Gordon-type arguments in the spectral theory of one-dimensional quasicrystals
- scientific article; zbMATH DE number 5279412 (Why is no real title available?)
- 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
Cited in
(35)- Palindromic richness
- A note on symmetries in the Rauzy graph and factor frequencies
- On low-complexity bi-infinite words and their factors
- Pattern avoidance by palindromes
- Specular sets
- Palindromic complexity of infinite words associated with simple Parry numbers
- A connection between palindromic and factor complexity using return words
- On highly potential words
- Palindromic closures using multiple antimorphisms
- Topological invariants for words of linear factor complexity
- Sturmian jungle (or garden?) On multiliteral alphabets
- ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
- Generalized Thue-Morse words and palindromic richness
- Sturmian and Episturmian Words
- Palindromes in infinite ternary words
- On the least number of palindromes contained in an infinite word
- 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
- Palindromic and abelian complexities in binary recurrent words of ultimate complexity n + 2
- Factor frequencies in languages invariant under symmetries preserving factor frequencies
- ALMOST RICH WORDS AS MORPHIC IMAGES OF RICH WORDS
- Morphic images of episturmian words having finite palindromic defect
- Upper bound for palindromic and factor complexity of rich words
- Complexity and palindromic defect of infinite words
- On theta-palindromic richness
- Weighted prefix normal words
- The reflection complexity of sequences over finite alphabets
- The asymptotic repetition threshold of sequences rich in palindromes
- On Brlek-Reutenauer conjecture
- Infinite words with finite defect
- \(N\)-factor complexity of the Fibonacci sequence on \(\mathbb{N}\) and the factor-counting sequences
- The limit of repetition thresholds of rich sequences
- Weighted prefix normal words: mind the gap
- Matrices of 3-iet preserving morphisms
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)
