Palindrome complexity.
From MaRDI portal
Publication:1853729
DOI10.1016/S0304-3975(01)00212-2zbMath1064.68074arXivmath/0106121OpenAlexW2912094370MaRDI QIDQ1853729
Julien Cassaigne, David Damanik, Jean-Paul Allouche, Michael Baake
Publication date: 22 January 2003
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0106121
Related Items (67)
Initial non-repetitive complexity of infinite words ⋮ Symmetric and congruent Rauzy fractals ⋮ 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 ⋮ Palindromic Complexity of Trees ⋮ Time-Space Trade-Offs for Longest Common Extensions ⋮ A connection between palindromic and factor complexity using return words ⋮ Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences ⋮ Palindromic prefixes and episturmian words ⋮ Derived sequences and the factor spectrum of the period-doubling sequence ⋮ On the least number of palindromes contained in an infinite word ⋮ Languages invariant under more symmetries: overlapping factors versus palindromic richness ⋮ Palindrome pattern matching ⋮ Enumeration of two dimensional palindromes ⋮ On palindromic factorization of words ⋮ Words with many palindrome pair factors ⋮ Palindromic length of words and morphisms in class \(\mathcal{P}\) ⋮ A counterexample to a question of Hof, Knill and Simon ⋮ A subquadratic algorithm for minimum palindromic factorization ⋮ Complexity and palindromic defect of infinite words ⋮ Counting distinct palindromes in a word in linear time ⋮ On factors of synchronized sequences ⋮ Open and closed factors in Arnoux-Rauzy words ⋮ HV-Palindromes in Two-Dimensional Words ⋮ Searching for Gapped Palindromes ⋮ Rich words in the block reversal of a word ⋮ Combinatoire de mots récurrents de complexitén+2 ⋮ Morphisms generating antipalindromic words ⋮ Some properties of the \(k\)-bonacci words on infinite alphabet ⋮ Sturmian and Episturmian Words ⋮ Time-space trade-offs for longest common extensions ⋮ The ring of \(k\)-regular sequences. II. ⋮ On extremal properties of the Fibonacci word ⋮ Sturmian jungle (or garden?) on multiliteral alphabets ⋮ On prefix palindromic length of automatic words ⋮ ENUMERATION AND DECIDABLE PROPERTIES OF AUTOMATIC SEQUENCES ⋮ Palindromic sequences generated from marked morphisms ⋮ Mirror substitutions and palindromic sequences ⋮ Palindrome Pattern Matching ⋮ Symmetrized \(\beta \)-integers ⋮ On \(k\)-abelian palindromes ⋮ ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS ⋮ About the number of \(C^\infty \)-words of form \(\widetilde wxw \) ⋮ Equations on palindromes and circular words ⋮ Characterizing Cantorian sets by entropy‐like quantities ⋮ A new characteristic property of rich words ⋮ Pattern avoidance by palindromes ⋮ Palindromic Ziv-Lempel and Crochemore factorizations of \(m\)-bonacci infinite words ⋮ Infinite words with finite defect ⋮ Language structure of pattern Sturmian words ⋮ On the least number of palindromes in two-dimensional words ⋮ Palindromic richness ⋮ Rich and Periodic-Like Words ⋮ On Sturmian and episturmian words, and related topics ⋮ 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 ⋮ On possible growths of arithmetical complexity ⋮ Sequences of low arithmetical complexity ⋮ Local symmetry dynamics in one-dimensional aperiodic lattices: a numerical study ⋮ Upper bound for palindromic and factor complexity of rich words ⋮ On a group theoretic generalization of the Morse-Hedlund theorem ⋮ Privileged factors in the Thue-Morse word -- a comparison of privileged words and palindromes ⋮ On a question of Hof, Knill and Simon on palindromic substitutive systems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The equation \(a_ M=b^ Nc^ P\) in a free group
- Une nouvelle propriété des suites de Rudin-Shapiro. (A new property of Rudin-Shapiro sequences)
- The ring of \(k\)-regular sequences
- Power of words and recognizability of fixpoints of a substitution
- Subword complexities of various classes of deterministic developmental languages without interactions
- Complexity and special factors
- Complexity for finite factors of infinite sequences
- Complexity of sequences and dynamical systems
- Sequences with subword complexity \(2n\)
- On the complexity of infinite sequences
- Factors of generalized Rudin-Shapiro sequences
- Palindromes in the Fibonacci word
- Palindrome complexity bounds for primitive substitution sequences
- Three distance theorems and combinatorics on words
- Episturmian words and episturmian morphisms
- Singular continuous spectrum for palindromic Schrödinger operators
- Palindromes and Sturmian words
- Local symmetries in the period-doubling sequence
- A note on palindromicity
- Complexité des facteurs des mots infinis engendrés par morphismes itérés
- Dimension des courbes planes, papiers plies et suites de Rudin-Shapiro
- Generalized Rudin-Shapiro sequences
- The number of factors in a paperfolding sequence
- Schrödinger operators with Rudin-Shapiro potentials are not palindromic
- Reconnaissabilité des substitutions et complexité des suites automatiques
- Les transformations de Chacon : combinatoire, structure géométrique, lien avec les systèmes de complexité $2n+1$
- Uniqueness Theorems for Periodic Functions
- Uniform tag sequences
- Sequences with minimal block growth
- Episturmian words and some constructions of de Luca and Rauzy
This page was built for publication: Palindrome complexity.
