Palindrome complexity.
From MaRDI portal
Abstract: We study the palindrome complexity of infinite sequences on finite alphabets, i.e., the number of palindromic factors (blocks) of given length occurring in a given sequence. We survey the known results and obtain new results for some sequences, in particular for Rote sequences and for fixed points of primitive morphisms of constant length belonging to the class P substitutions of Hof-Knill-Simon. We also give an upper bound for the palindrome complexity of a sequence in terms of its (block-)complexity.
Recommendations
- Total palindrome complexity of finite words
- Palindromic length in linear time
- Palindromic complexity of trees
- scientific article; zbMATH DE number 5501412
- ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
- Palindromic richness
- scientific article; zbMATH DE number 3966175
- On the numbers of palindromes
- A note on palindromicity
- Complexity and palindromic defect of infinite words
Cites work
- scientific article; zbMATH DE number 98759 (Why is no real title available?)
- scientific article; zbMATH DE number 3517961 (Why is no real title available?)
- scientific article; zbMATH DE number 1064716 (Why is no real title available?)
- scientific article; zbMATH DE number 1737190 (Why is no real title available?)
- scientific article; zbMATH DE number 1413186 (Why is no real title available?)
- scientific article; zbMATH DE number 5051582 (Why is no real title available?)
- scientific article; zbMATH DE number 5051583 (Why is no real title available?)
- A note on palindromicity
- Complexity and special factors
- Complexity for finite factors of infinite sequences
- Complexity of sequences and dynamical systems
- Complexité des facteurs des mots infinis engendrés par morphismes itérés
- Dimension des courbes planes, papiers plies et suites de Rudin-Shapiro
- Episturmian words and episturmian morphisms
- Episturmian words and some constructions of de Luca and Rauzy
- Factors of generalized Rudin-Shapiro sequences
- Generalized Rudin-Shapiro sequences
- Generalized model sets and dynamical systems
- Gordon-type arguments in the spectral theory of one-dimensional quasicrystals
- Les transformations de Chacon : combinatoire, structure géométrique, lien avec les systèmes de complexité $2n+1$
- Local symmetries in the period-doubling sequence
- On the complexity of infinite sequences
- Palindrome complexity bounds for primitive substitution sequences
- Palindromes and Sturmian words
- Palindromes and two-dimensional Sturmian sequences
- Palindromes in the Fibonacci word
- Power of words and recognizability of fixpoints of a substitution
- Reconnaissabilité des substitutions et complexité des suites automatiques
- Schrödinger operators with Rudin-Shapiro potentials are not palindromic
- Sequences with minimal block growth
- Sequences with subword complexity \(2n\)
- Singular continuous spectrum for palindromic Schrödinger operators
- Subword complexities of various classes of deterministic developmental languages without interactions
- The equation \(a_ M=b^ Nc^ P\) in a free group
- The number of factors in a paperfolding sequence
- The ring of k-regular sequences
- Three distance theorems and combinatorics on words
- Une nouvelle propriété des suites de Rudin-Shapiro. (A new property of Rudin-Shapiro sequences)
- Uniform tag sequences
- Uniqueness Theorems for Periodic Functions
Cited in
(73)- Palindrome pattern matching
- On palindromic factorization of words
- Complexity and palindromic defect of infinite words
- Counting distinct palindromes in a word in linear time
- Palindrome pattern matching
- Equations on palindromes and circular words
- A note on palindromicity
- On a question of Hof, Knill and Simon on palindromic substitutive systems
- Palindromic complexity of trees
- Enumeration of two dimensional palindromes
- A counterexample to a question of Hof, Knill and Simon
- Enumeration and decidable properties of automatic sequences
- A subquadratic algorithm for minimum palindromic factorization
- On factors of synchronized sequences
- Palindromic prefixes and episturmian words
- Words with many palindrome pair factors
- Pattern avoidance by palindromes
- On the least number of palindromes in two-dimensional words
- Searching for gapped palindromes
- Symmetrized \(\beta \)-integers
- Infinite words with finite defect
- Initial non-repetitive complexity of infinite words
- Palindromic richness
- About the number of C^ -words of form wxw
- Open and closed factors in Arnoux-Rauzy words
- On k-abelian palindromes
- On Sturmian and episturmian words, and related topics
- Time-Space Trade-Offs for Longest Common Extensions
- Upper bound for palindromic and factor complexity of rich words
- Uniform spectral properties of one-dimensional quasicrystals. IV. Quasi-Sturmian potentials
- Sturmian jungle (or garden?) On multiliteral alphabets
- Symmetric and congruent Rauzy fractals
- Palindrome complexity bounds for primitive substitution sequences
- Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences
- Palindromic Ziv-Lempel and Crochemore factorizations of \(m\)-bonacci infinite words
- The ring of \(k\)-regular sequences. II.
- A new characteristic property of rich words
- Factor versus palindromic complexity of uniformly recurrent infinite words
- Palindromic complexity of infinite words associated with simple Parry numbers
- A connection between palindromic and factor complexity using return words
- Combinatoire de mots récurrents de complexitén+2
- Rich and Periodic-Like Words
- Derived sequences and the factor spectrum of the period-doubling sequence
- A note on symmetries in the Rauzy graph and factor frequencies
- Mirror substitutions and palindromic sequences
- Language structure of pattern Sturmian words
- Some properties of the \(k\)-bonacci words on infinite alphabet
- Some properties of the Tribonacci sequence
- ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
- On possible growths of arithmetical complexity
- Palindromic length of words and morphisms in class \(\mathcal{P}\)
- On extremal properties of the Fibonacci word
- On the least number of palindromes contained in an infinite word
- HV-Palindromes in Two-Dimensional Words
- Palindrome recognition using a multidimensional tape.
- Characterizing Cantorian sets by entropy‐like quantities
- On the complexity functions of Sturmian words
- Palindromic sequences generated from marked morphisms
- Local symmetry dynamics in one-dimensional aperiodic lattices: a numerical study
- Time-space trade-offs for longest common extensions
- Total palindrome complexity of finite words
- Searching for Gapped Palindromes
- Rich words in the block reversal of a word
- Privileged factors in the Thue-Morse word -- a comparison of privileged words and palindromes
- Properties of palindromes in finite words
- The complexity of \(C^{b\omega }\)-words of the form \(\tilde w xw\)
- Sequences of low arithmetical complexity
- Morphisms generating antipalindromic words
- Languages invariant under more symmetries: overlapping factors versus palindromic richness
- On prefix palindromic length of automatic words
- Proof of a conjecture of Krawchuk and Rampersad on the cyclic complexity of the Thue-Morse sequence
- Sturmian and Episturmian Words
- On a group theoretic generalization of the Morse-Hedlund theorem
This page was built for publication: Palindrome complexity.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853729)
