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)- On the complexity functions of Sturmian words
- Proof of a conjecture of Krawchuk and Rampersad on the cyclic complexity of the Thue-Morse sequence
- Characterizing Cantorian sets by entropy‐like quantities
- HV-Palindromes in Two-Dimensional Words
- Symmetrized \(\beta \)-integers
- Combinatoire de mots récurrents de complexitén+2
- Enumeration of two dimensional palindromes
- Some properties of the Tribonacci sequence
- About the number of \(C^\infty \)-words of form \(\widetilde wxw \)
- On possible growths of arithmetical complexity
- Sequences of low arithmetical complexity
- On extremal properties of the Fibonacci word
- ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
- Palindrome pattern matching
- Palindrome pattern matching
- On palindromic factorization of words
- Time-space trade-offs for longest common extensions
- Enumeration and decidable properties of automatic sequences
- Total palindrome complexity of finite words
- Complexity and palindromic defect of infinite words
- A note on palindromicity
- Palindromic length of words and morphisms in class \(\mathcal{P}\)
- Sturmian jungle (or garden?) On multiliteral alphabets
- Some properties of the \(k\)-bonacci words on infinite alphabet
- Initial non-repetitive complexity of infinite words
- Infinite words with finite defect
- Counting distinct palindromes in a word in linear time
- Equations on palindromes and circular words
- Palindrome complexity bounds for primitive substitution sequences
- Language structure of pattern Sturmian words
- Morphisms generating antipalindromic words
- A subquadratic algorithm for minimum palindromic factorization
- A note on symmetries in the Rauzy graph and factor frequencies
- Palindromic prefixes and episturmian words
- On factors of synchronized sequences
- On Sturmian and episturmian words, and related topics
- Derived sequences and the factor spectrum of the period-doubling sequence
- Rich and Periodic-Like Words
- The complexity of \(C^{b\omega }\)-words of the form \(\tilde w xw\)
- Uniform spectral properties of one-dimensional quasicrystals. IV. Quasi-Sturmian potentials
- Palindrome recognition using a multidimensional tape.
- On a group theoretic generalization of the Morse-Hedlund theorem
- Searching for gapped palindromes
- Mirror substitutions and palindromic sequences
- Languages invariant under more symmetries: overlapping factors versus palindromic richness
- Words with many palindrome pair factors
- Palindromic Ziv-Lempel and Crochemore factorizations of \(m\)-bonacci infinite words
- Upper bound for palindromic and factor complexity 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
- Rich words in the block reversal of a word
- Palindromic complexity of trees
- On the least number of palindromes contained in an infinite word
- A new characteristic property of rich words
- Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences
- Palindromic sequences generated from marked morphisms
- Properties of palindromes in finite words
- Local symmetry dynamics in one-dimensional aperiodic lattices: a numerical study
- Pattern avoidance by palindromes
- On a question of Hof, Knill and Simon on palindromic substitutive systems
- Sturmian and Episturmian Words
- Privileged factors in the Thue-Morse word -- a comparison of privileged words and palindromes
- Palindromic richness
- The ring of \(k\)-regular sequences. II.
- Searching for Gapped Palindromes
- Open and closed factors in Arnoux-Rauzy words
- On \(k\)-abelian palindromes
- Symmetric and congruent Rauzy fractals
- On the least number of palindromes in two-dimensional words
- Time-Space Trade-Offs for Longest Common Extensions
- On prefix palindromic length of automatic words
- A counterexample to a question of Hof, Knill and Simon
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)
