The reflection complexity of sequences over finite alphabets
The authors introduce the \textit{reflection complexity} \(r_x(n)\) of an infinite word \(x\) as the number of factors of length \(n\) occurring in \(x\) up to reversing the order of symbols: words \(a_1a_2\cdots a_n\) and \(a_n\cdots a_2 a_1\) are considered as equal. Clearly, \(\frac{1}{2} p_x(n)\leq r_x(n) \leq p_x(n)\), where \(p_x(n)\) is the usual factor complexity of \(x\), that is, the number of its factors of length \(n\). More precisely, equalities involving the number of palindromes, unreflected and reflected factors of \(x\) are also easy to verify. Moreover, if \(x\) is uniformly recurrent, then either all factors are reflected, or there are no reflected factors starting from some length, and it is possible to rapidly classify the reflection complexity as either a half of \((p_x(n)+\text{the number of palindromes of length } n\)), or just eventually \(p_x(n)\).\N\NThe paper contains many nice results on words with different relations among the factor complexity, the reflection complexity and the number of palindromes, and several structural facts, including the proof that if \(x\) is \(k\)-automatic, then \(r_x\) is computably \(k\)-regular.
- A connection between palindromic and factor complexity using return words
- A generalization of automatic sequences
- A new complexity function for words based on periodicity
- A new complexity function, repetitions in Sturmian words, and irrationality exponents of Sturmian numbers
- A note on differentiable palindromes.
- A note on palindromicity
- A note on the maximum number of k-powers in a finite word
- Abelian combinatorics on words: a survey
- An approximate distribution for the maximum order complexity
- Another generalization of abelian equivalence: binomial complexity of infinite words
- Automatic Sequences
- Complexity and palindromic defect of infinite words
- Complexity for finite factors of infinite sequences
- Complexity of sequences and dynamical systems
- Complexity of sequences defined by billiard in the cube
- Complexity of trajectories in rectangular billiards
- Complexité des facteurs des mots infinis engendrés par morphismes itérés
- Cyclic complexity of words
- Derived sequences of complementary symmetric Rote sequences
- Enumeration of factors in the Thue-Morse word
- Episturmian words and some constructions of de Luca and Rauzy
- Episturmian words: a survey
- Eulerian entropy and non-repetitive subword complexity
- Factor versus palindromic complexity of uniformly recurrent infinite words
- Factors of generalized Rudin-Shapiro sequences
- Generalized perturbed symmetry
- scientific article; zbMATH DE number 3871492 (Why is no real title available?)
- scientific article; zbMATH DE number 3739694 (Why is no real title available?)
- scientific article; zbMATH DE number 3505007 (Why is no real title available?)
- scientific article; zbMATH DE number 1024080 (Why is no real title available?)
- scientific article; zbMATH DE number 1737190 (Why is no real title available?)
- scientific article; zbMATH DE number 6893715 (Why is no real title available?)
- scientific article; zbMATH DE number 1916667 (Why is no real title available?)
- scientific article; zbMATH DE number 808803 (Why is no real title available?)
- scientific article; zbMATH DE number 3205709 (Why is no real title available?)
- scientific article; zbMATH DE number 7069796 (Why is no real title available?)
- scientific article; zbMATH DE number 5051582 (Why is no real title available?)
- scientific article; zbMATH DE number 2235059 (Why is no real title available?)
- scientific article; zbMATH DE number 3095523 (Why is no real title available?)
- Introducing privileged words: privileged complexity of Sturmian words
- Les transformations de Chacon : combinatoire, structure géométrique, lien avec les systèmes de complexité 2n+1
- Lie complexity of words
- Minimal symbolic flows having minimal block growth
- New string attractor-based complexities for infinite words
- On a generalization of abelian equivalence and complexity of infinite words
- On a group theoretic generalization of the Morse-Hedlund theorem
- On a new notion of complexity on infinite words
- On abelian and additive complexity in infinite words
- On factor complexity of morphic sequences
- On factors of synchronized sequences
- On Subword Complexity of Morphic Sequences
- On the Complexity of Finite Sequences
- On the complexity of infinite sequences
- On the least number of palindromes contained in an infinite word
- On the number of squares in a finite word
- On the subword complexity of Thue-Morse polynomial extractions
- Palindrome complexity.
- Palindromes and Sturmian words
- Palindromic complexity of codings of rotations
- Progress in Cryptology - INDOCRYPT 2003
- Relationally Periodic Sequences and Subword Complexity
- Schrödinger operators with Rudin-Shapiro potentials are not palindromic
- Sequence entropy and the maximal pattern complexity of infinite words
- Sequences of symmetry groups of infinite words
- Sequences with minimal block growth II
- Sequences with subword complexity \(2n\)
- Singular continuous spectrum for palindromic Schrödinger operators
- Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
- Some Theorems on Fourier Coefficients
- Sturmian and Episturmian Words
- Sturmian jungle (or garden?) On multiliteral alphabets
- Symbolic dynamics.
- The Lempel–Ziv Complexity of Fixed Points of Morphisms
- The Logical Approach to Automatic Sequences
- Uniform spectral properties of one-dimensional quasicrystals. IV. Quasi-Sturmian potentials
- Upper bound for palindromic and factor complexity of rich words
This page was built for publication: The reflection complexity of sequences over finite alphabets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6905974)
