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