# doc. Ing. Štěpán Starosta, Ph.D.

Vice-Dean for Science and Research

## Publications

### Binary Codes that Do Not Preserve Primitivity

Authors
Holub, S.; Raska, M.; Starosta, Š.
Year
2022
Published
IJCAR 2022: Automated Reasoning. Cham: Springer, 2022. p. 369-387. Lecture Notes in Computer Science. vol. 13385. ISSN 0302-9743. ISBN 978-3-031-10768-9.
Type
Proceedings paper
Departments
Annotation
A code X is not primitivity preserving if there is a primitive list w is an element of lists X whose concatenation is imprimitive. We formalize a full characterization of such codes in the binary case in the proof assistant Isabelle/HOL. Part of the formalization, interesting on its own, is a description of {x, y}-interpretations of the square xx if |y| <= |x|. We also provide a formalized parametric solution of the related equation x(j) y(k) = z(l).

### A characterization of Sturmian sequences by indistinguishable asymptotic pairs

Authors
Barbieri, S.; Labbé, S.; Starosta, Š.
Year
2021
Published
European Journal of Combinatorics. 2021, 95 ISSN 0195-6698.
Type
Article
Departments
Annotation
We give a new characterization of biinfinite Sturmian sequences in terms of indistinguishable asymptotic pairs. Two asymptotic sequences on a full -shift are indistinguishable if the sets of occurrences of every pattern in each sequence coincide up to a finitely supported permutation. This characterization can be seen as an extension to biinfinite sequences of Pirillo’s theorem which characterizes Christoffel words. Furthermore, we provide a full characterization of indistinguishable asymptotic pairs on arbitrary alphabets using substitutions and biinfinite characteristic Sturmian sequences. The proof is based on the well-known notion of derived sequences.

### Binary intersection formalized

Authors
Holub, Š.; Starosta, Š.
Year
2021
Published
Theoretical Computer Science. 2021, 866 14-24. ISSN 0304-3975.
Type
Article
Departments
Annotation
We provide a reformulation and a formalization of the classical result by Juhani Karhumäki characterizing intersections of two languages of the form $\{x,y\}^* \cap \{u,v\}^*$. We use the terminology of morphisms which allows to formulate the result in a shorter and more transparent way, and we formalize the result in the proof assistant Isabelle/HOL.

### Combinatorics on Words Basics

Authors
Holub, Š.; Raška, M.; Starosta, Š.
Year
2021
Published
Archive of Formal Proofs. 2021, ISSN 2150-914X.
Type
Article
Departments
Annotation
We formalize basics of Combinatorics on Words. This is an extension of existing theories on lists. We provide additional properties related to prefix, suffix, factor, length and rotation. The topics include prefix and suffix comparability, mismatch, word power, total and reversed morphisms, border, periods, primitivity and roots. We also formalize basic, mostly folklore results related to word equations: equidivisibility, commutation and conjugation. Slightly advanced properties include the Periodicity lemma (often cited as the Fine and Wilf theorem) and the variant of the Lyndon-Schützenberger theorem for words. We support the algebraic point of view which sees words as generators of submonoids of a free monoid. This leads to the concepts of the (free) hull, the (free) basis (or code).

### Formalization of Basic Combinatorics on Words

Authors
Holub, Š.; Starosta, Š.
Year
2021
Published
12th International Conference on Interactive Theorem Proving (ITP 2021). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2021. p. 22:1-22:17. ISSN 1868-8969. ISBN 978-3-95977-188-7.
Type
Proceedings paper
Departments
Annotation
Combinatorics on Words is a rather young domain encompassing the study of words and formal languages. An archetypal example of a task in Combinatorics on Words is to solve the equation x ⋅ y = y ⋅ x, i.e., to describe words that commute. This contribution contains formalization of three important classical results in Isabelle/HOL. Namely i) the Periodicity Lemma (a.k.a. the theorem of Fine and Wilf), including a construction of a word proving its optimality; ii) the solution of the equation x^a ⋅ y^b = z^c with 2 ≤ a,b,c, known as the Lyndon-Schützenberger Equation; and iii) the Graph Lemma, which yields a generic upper bound on the rank of a solution of a system of equations. The formalization of those results is based on an evolving toolkit of several hundred auxiliary results which provide for smooth reasoning within more complex tasks.

### Graph Lemma

Authors
Holub, Š.; Starosta, Š.
Year
2021
Published
Archive of Formal Proofs. 2021, ISSN 2150-914X.
Type
Article
Departments
Annotation
Graph lemma quantifies the defect effect of a system of word equations. That is, it provides an upper bound on the rank of the system. We formalize the proof based on the decomposition of a solution into its free basis. A direct application is an alternative proof of the fact that two noncommuting words form a code.

### Lyndon words

Authors
Holub, Š.; Starosta, Š.
Year
2021
Published
Archive of Formal Proofs. 2021, ISSN 2150-914X.
Type
Article
Departments
Annotation
Lyndon words are words lexicographically minimal in their conjugacy class. We formalize their basic properties and characterizations, in particular the concepts of the longest Lyndon suffix and the Lyndon factorization. Most of the work assumes a fixed lexicographical order. Nevertheless we also define the smallest relation guaranteeing lexicographical minimality of a given word (in its conjugacy class).

### Lyndon words formalized in Isabelle/HOL

Authors
Holub, Š.; Starosta, Š.
Year
2021
Published
Developments in Language Theory. Springer, Cham, 2021. p. 217-228. Lecture Notes in Computer Science. vol. 12811. ISSN 0302-9743. ISBN 978-3-030-81507-3.
Type
Proceedings paper
Departments
Annotation
We present a formalization of Lyndon words and basic relevant results in Isabelle/HOL. We give a short review of Isabelle/HOL and focus on challenges that arise in this formalization. The presented formalization is based on an ongoing larger project of formalization of combinatorics on words.

### On Sturmian substitutions closed under derivation

Authors
Pelantová, E.; Starosta, Š.
Year
2021
Published
Theoretical Computer Science. 2021, 867 128-139. ISSN 0304-3975.
Type
Article
Departments
Annotation
Occurrences of a factor $w$ in an infinite uniformly recurrent sequence ${\bf u}$ can be encoded by an infinite sequence over a finite alphabet. This sequence is usually denoted ${\bf d_{\bf u}}(w)$ and called the derived sequence to $w$ in ${\bf u}$. If $w$ is a prefix of a fixed point ${\bf u}$ of a primitive substitution $\varphi$, then by Durand's result from 1998, the derived sequence ${\bf d_{\bf u}}(w)$ is fixed by a primitive substitution $\psi$ as well. For a non-prefix factor $w$, the derived sequence ${\bf d_{\bf u}}(w)$ is fixed by a substitution only exceptionally. To study this phenomenon we introduce a new notion: A finite set $M$ of substitutions is said to be closed under derivation if the derived sequence ${\bf d_{\bf u}}(w)$ to any factor $w$ of any fixed point ${\bf u}$ of $\varphi \in M$ is fixed by a morphism $\psi \in M$. In our article we characterize the Sturmian substitutions which belong to a set $M$ closed under derivation. The characterization uses either the slope and the intercept of its fixed point or its S-adic representation.

### Bounds on the period of the continued fraction after a Möbius transformation

Authors
Year
2020
Published
Journal of Number Theory. 2020, 212 122-172. ISSN 0022-314X.
Type
Article
Departments
Annotation
We study Möbius transformations (also known as linear fractional transformations) of quadratic numbers. We construct explicit upper and lower bounds on the period of the continued fraction expansion of a transformed number as a function of the period of the continued fraction expansion of the original number. We provide examples that show that the bound is sharp.

### Characterization of circular D0L-systems

Authors
Year
2019
Published
Theoretical Computer Science. 2019, 790 131-137. ISSN 0304-3975.
Type
Article
Departments
Annotation
We give a characterization of circularity of a D0L-system. The characterizing condition is simple to verify and yields an efficient algorithm. To derive it, we prove that every non-circular D0L-system contains arbitrarily long repetitions. This result was already published in 1993 by Mignosi and Séébold, however their proof is only a sketch. We give a complete proof that, in addition, is valid for a slightly relaxed definition of circularity, called weak circularity.

### On Substitutions Closed Under Derivation: Examples

Authors
Košík, V.; Starosta, Š.
Year
2019
Published
Combinatorics on Words. WORDS 2019.. Springer, Cham, 2019. p. 226-237. Lecture Notes in Computer Science. vol. 11682. ISSN 0302-9743. ISBN 978-3-030-28795-5.
Type
Proceedings paper
Departments
Annotation
We study infinite words fixed by a morphism and their derived words. A derived word is a coding of return words to a factor. We exhibit two examples of sets of morphisms which are closed under derivation—any derived word with respect to any factor of the fixed point is again fixed by a morphism from this set. The first example involves standard episturmian morphisms, and the second concerns the period doubling morphism.

### Fixed Points of Sturmian Morphisms and Their Derivated Words

Authors
Klouda, K.; Medková, K.; Pelantová, E.; Starosta, Š.
Year
2018
Published
Theoretical Computer Science. 2018, 743 23-37. ISSN 0304-3975.
Type
Article
Departments
Annotation
Any infinite uniformly recurrent word u can be written as concatenation of a finite number of return words to a chosen prefix w of u. Ordering of the return words to w in this concatenation is coded by derivated word d_u(w). In 1998, Durand proved that a fixed point u of a primitive morphism has only finitely many derivated words d_u(w) and each derivated word d_u(w) is fixed by a primitive morphism as well. In our article we focus on Sturmian words fixed by a primitive morphism. We provide an algorithm which to a given Sturmian morphism ψ lists the morphisms fixing the derivated words of the Sturmian word u = psi(u). We provide a sharp upper bound on length of the list.

### Exchange of three intervals: substitutions and palindromicity

Authors
Masáková, Z.; Pelantová, E.; Starosta, Š.
Year
2017
Published
European Journal of Combinatorics. 2017, 62 217-231. ISSN 0195-6698.
Type
Article
Departments
Annotation
We study purely morphic words coding symmetric non-degenerate three interval exchange transformation which are known to be palindromic, i.e., they contain infinitely many palindromes. We prove that such words are fixed by a conjugate to a morphism of class $P$, that is a morphism such that each letter $a$ is mapped to $pp_a$ where $p$ and $p_a$ are both palindromes. We thus provide a new family of palindromic infinite words satisfying the conjecture of Hof, Knill and Simon. Given a morphism fixing such word, we give a formula to determine the parameters of the underlying three interval exchange and the intercept of the word.

### On the Zero Defect Conjecture

Authors
Labbé, S.; Pelantová, E.; Starosta, Š.
Year
2017
Published
European Journal of Combinatorics. 2017, 62 132-146. ISSN 0195-6698.
Type
Article
Departments
Annotation
Brlek et al., conjectured in 2008 that any fixed point of a primitive morphism with finite palindromic defect is either periodic or its palindromic defect is zero. Bucci and Vaslet disproved this conjecture in 2012 by a counterexample over ternary alphabet. We prove that the conjecture is valid on binary alphabet. We also describe a class of morphisms over multiliteral alphabet for which the conjecture still holds. The proof is based on properties of extension graphs.

### On Words with the Zero Palindromic Defect

Authors
Pelantová, E.; Starosta, Š.
Year
2017
Published
Combinatorics on Words: 11th International Conference, WORDS 2017, Montréal, QC, Canada, September 11-15, 2017, Proceedings. Basel: Springer, 2017. p. 59-71. Lecture Notes in Computer Science. vol. 10432. ISSN 0302-9743. ISBN 9783319663951.
Type
Proceedings paper
Departments
Annotation
We study the set of finite words with zero palindromic defect, i.e., words rich in palindromes. This set is factorial, but not recurrent. We focus on description of pairs of rich words which cannot occur simultaneously as factors of a longer rich word.

### Constructions of words rich in palindromes and pseudopalindromes

Authors
Pelantová, E.; Starosta, Š.
Year
2016
Published
Discrete Mathematics and Theoretical Computer Science. 2016, 18(3), 1-26. ISSN 1462-7264.
Type
Article
Departments
Annotation
A narrow connection between infinite binary words rich in classical palindromes and infinite binary words rich simultaneously in palindromes and pseudopalindromes (the so-called H-rich words) is demonstrated. The correspondence between rich and H-rich words is based on the operation S acting over words over the alphabet {0,1} and defined by S(u0u1u2…)=v1v2v3…, where vi=ui−1+uimod2. The operation S enables us to construct a new class of rich words and a new class of H-rich words. Finally, the operation S is considered on the multiliteral alphabet Zm as well and applied to the generalized Thue--Morse words. As a byproduct, new binary rich and H-rich words are obtained by application of S on the generalized Thue--Morse words over the alphabet Z4.

### ITINERARIES INDUCED BY EXCHANGE OF THREE INTERVALS

Authors
Masáková, Z.; Pelantová, E.; Starosta, Š.
Year
2016
Published
Acta Polytechnica. 2016, 56(6), 462-471. ISSN 1805-2363.
Type
Article
Departments
Annotation
We focus on a generalization of the three gap theorem well known in the framework of exchange of two intervals. For the case of three intervals, our main result provides an analogue of this result implying that there are at most 5 gaps. To derive this result, we give a detailed description of the return times to a subinterval and the corresponding itineraries.

### Markov constant and quantum instabilities

Authors
Pelantová, E.; Starosta, Š.; Znojil, Miloslav
Year
2016
Published
Journal of Physics A: Mathematical and Theoretical. 2016, 49(15), 1-19. ISSN 1751-8113.
Type
Article
Departments
Annotation
For a qualitative analysis of spectra of certain two-dimensional rectangular-well quantum systems several rigorous methods of number theory are shown productive and useful. These methods (and, in particular, a generalization of the concept of Markov constant known in Diophantine approximation theory) are shown to provide a new mathematical insight in the phenomenologically relevant occurrence of anomalies in the spectra. Our results may inspire methodical innovations ranging from the description of the stability properties of metamaterials and of certain hiddenly unitary quantum evolution models up to the clarification of the mechanisms of occurrence of ghosts in quantum cosmology.

### Morphic images of episturmian words having finite palindromic defect

Authors
Year
2016
Published
European Journal of Combinatorics. 2016, 51 359-371. ISSN 0195-6698.
Type
Article
Departments
Annotation
We study morphisms from certain classes and their action on episturmian words.The first class is $P_{ret}$. In general, a morphism of class $P_{ret}$ can map an infinite word having zero palindromic defect to a word having infinite palindromic defect. We show that the image of an episturmian word, which has zero palindromic defect, under a morphism of class $P_{ret}$ has always its palindromic defect finite. We also focus on letter-to-letter morphisms to binary alphabet: we show that images of ternary episturmian words under such morphisms have zero palindromic defect. These results contribute to the study of an unsolved question of characterization of morphisms that preserve finite, or even zero, palindromic defect. They also enable us to construct new examples of binary words having zero or finite $H$-palindromic defect, where $H = {{rm Id}, R, E, RE }$ is the group generated by both involutory antimorphisms on a binary alphabet.

### An algorithm for enumerating all infinite repetitions in a D0L-system

Authors
Year
2015
Published
Journal of Discrete Algorithms. 2015, 33 130-138. ISSN 1570-8667.
Type
Article
Departments
Annotation
We describe a simple algorithm that finds all primitive words v such that v^k is a factor of the language of a given D0L-system for all k. It follows that the number of such words is finite. This polynomial-time algorithm can be also used to decide whether a D0L-system is repetitive.

### Factor Complexity of Letter-to-Letter Images od Arnoux-Rauzy Words

Authors
Starosta, Š.; Veselý, V.
Year
2015
Published
Combinatorics on Words, 10th International Conference WORDS 2015. Local Proceedings.. Kiel: Department of Computer Science, Faculty of Engineering, Kiel University, 2015. pp. 47-61. Kiel Computer Science Series. ISSN 2193-6781.
Type
Proceedings paper
Departments
Annotation
We prove that if u is a k-ary Arnoux-Rauzy word and pi a non-trivial letter-to-letter homomorphism, then the word pi(u) has its factor complexity equal to (k-1)n+q for all sufficiently large n and some integer q.

### Interval Exchange Words and the Question of Hof, Knill, and Simon

Authors
Masáková, Z.; Pelantová, E.; Starosta, Š.
Year
2015
Published
Developments in Language Theory, 19th International Conference, DLT 2015. Cham: Springer International Publishing, 2015. pp. 377-388. Lecture Notes in Computer Science. ISSN 0302-9743. ISBN 978-3-319-21499-3.
Type
Proceedings paper
Departments
Annotation
We consider words coding non-degenerate 3 interval exchange transformation. It is known that such words contain infinitely many palindromic factors. We show that for any morphism $xi$ fixing such a word, either $xi$ or $xi^2$ is conjugate to a class $P$ morphism. By this, we provide a new family of palindromic infinite words satisfying the conjecture of Hof, Knill and Simon, as formulated by Tan.

### On the partitions with Sturmian-like refinements

Authors
Kupsa, M.; Starosta, Š.
Year
2015
Published
Discrete and Continuous Dynamical Systems - Series A. 2015, 35(8), 3483-3501. ISSN 1078-0947.
Type
Article
Departments
Annotation
In the dynamics of a rotation of the unit circle by an irrational angle $alpha in (0,1)$, we study the evolution of partitions whose atoms are finite unions of left-closed right-open intervals with endpoints lying on the past trajectory of the point 0. Unlike the standard framework, we focus on partitions whose atoms are disconnected sets. We show that the refinements of these partitions eventually coincide with the refinements of a preimage of the Sturmian partition, which consists of two intervals $[0,1-alpha)$ and $[1-alpha,1)$. In particular, the refinements of the partitions eventually consist of connected sets, i.e., intervals. We reformulate this result in terms of Sturmian subshifts: we show that for every non-trivial factor mapping from a one-sided Sturmian subshift, satisfying a mild technical assumption, the sliding block code of sufficiently large length induced by the mapping is injective.

### Open Computing with SageMath

Authors
Year
2015
Published
Pokroky matematiky, fyziky a astronomie. 2015, 60(4), 300-313. ISSN 0032-2423.
Type
Article
Departments
Annotation
We present basic usage of open computer algebra system SageMath and we discuss the need of openness of mathematical software.

### Palindromic closures using multiple antimorphisms

Authors
Jajcayová, T.; Pelantová, E.; Starosta, Š.
Year
2014
Published
Theoretical Computer Science. 2014, 533 37-45. ISSN 0304-3975.
Type
Article
Departments
Annotation
A generalized pseudostandard word $bf u$, as introduced in 2006 by de Luca and De Luca, is given by a directive sequence of letters from an alphabet ${cal A}$ and by a directive sequence of involutory antimorphisms acting on ${cal A}^*$. Prefixes of $bf u$ with increasing length are constructed using pseudopalindromic closure operator. We show that generalized Thue--Morse words ${bf t}_{b,m}$, with $b, m in N$ and $b, m geq 2$, are generalized pseudostandard words if and only if ${bf t}_{b,m}$ is a periodic word or $b leq m$. This extends the result of de Luca and De Luca obtained for the classical Thue--Morse words.

### Palindromic richness for languages invariant under more symmetries

Authors
Pelantová, E.; Starosta, Š.
Year
2014
Published
Theoretical Computer Science. 2014, 518 42-63. ISSN 0304-3975.
Type
Article
Departments
Annotation
For a given finite group $G$ consisting of morphisms and antimorphisms of a free monoid $mathcal{A}^*$, we study infinite words with language closed under the group $G$. We focus on the notion of $G$-richness which describes words rich in generalized palindromic factors, i.e., in factors $w$ satisfying $Theta(w) = w$ for some antimorphism $Theta in G$. We give several equivalent descriptions which are generalizations of known characterizations of rich words (in the terms of classical palindromes) and show two examples of $G$-rich words.

### Languages invariant under more symmetries: overlapping factors versus palindromic richness

Authors
Pelantová, E.; Starosta, Š.
Year
2013
Published
Discrete Mathematics. 2013, 313(21), 2432-2445. ISSN 0012-365X.
Type
Article
Departments
Annotation
Factor complexity $mathcal{C}$ and palindromic complexity $mathcal{P}$ of infinite words with language closed under reversal are known to be related by the inequality $mathcal{P}(n) + mathcal{P}(n+1) leq 2 + mathcal{C}(n+1)-mathcal{C}(n)$ for any $nin mathbb{N}$,. Words for which the equality is attained for any $n$ are usually called rich in palindromes. We show that rich words contain infinitely many overlapping factors. We study words whose languages are invariant under a finite group $G$ of symmetries. For such words we prove a stronger version of the above inequality. We introduce the notion of $G$-palindromic richness and give several examples of $G$-rich words, including the Thue-Morse sequence as well.

### Proof of the Brlek-Reutenauer conjecture

Authors
Balková, L.; Pelantová, E.; Starosta, Š.
Year
2013
Published
Theoretical Computer Science. 2013, 475 120-125. ISSN 0304-3975.
Type
Article
Departments
Annotation
Brlek and Reutenauer conjectured that any infinite word u with language closed under reversal satisfies the equality 2D(u)= sum_{n=0}^{+infty}T_u(n) in which D(u) denotes the defect of u and T_u(n) denotes C_u(n+1)-C_u(n)+2 - P_u(n)-P_u(n+1), where C_u(n) and P_u(n) are the factor and palindromic complexity of u, respectively. This conjecture was verified for periodic words by Brlek and Reutenauer themselves. Using their results for periodic words, we have recently proved the conjecture for uniformly recurrent words. In the present article we prove the conjecture in its general version by a new method without exploiting the result for periodic words.

### The Rauzy Gasket

Authors
Arnoux, P.; Starosta, Š.
Year
2013
Published
Further Developments in Fractals and Related Fields. Boston: Birkhaeuser, 2013. p. 1-23. Trends in Mathematics. ISBN 978-0-8176-8399-3.
Type
Book chapter
Departments
Annotation
We define the Rauzy gasket, a subset of the standard 2-dimensional simplex associated with letter frequencies of ternary episturmian words. We prove that the Rauzy gasket is homeomorphic to the usual Sierp'inski gasket (by a 2-dimensional generalization of the Minkowski ? function) and to the Apollonian gasket (by a map which is smooth on the boundary of the simplex). We prove that it is also homothetic to the invariant set of the fully subtractive algorithm, hence of measure 0.

### Almost rich words as morphic images of rich words

Authors
Pelantová, E.; Starosta, Š.
Year
2012
Published
International Journal of Foundations of Computer Science. 2012, 23(5), 1067-1083. ISSN 0129-0541.
Type
Article
Departments
Annotation
We focus on Theta-rich and almost Theta-rich words over a finite alphabet , where Theta is an involutive antimorphism over . We show that any recurrent almost Theta-rich word u is an image of a recurrent Theta'-rich word under a suitable morphism, where Theta' is also an involutive antimorphism. Moreover, if the word u is uniformly recurrent, we show that Theta' can be set to the reversal mapping. We also treat one special case of almost Theta-rich words: we show that every Theta-standard word with seed is an image of an Arnoux-Rauzy word.

### Corrigendum: "On Brlek-Reutenauer Conjecture"

Authors
Balková, L.; Pelantová, E.; Starosta, Š.
Year
2012
Published
Theoretical Computer Science. 2012, 465 73-74. ISSN 0304-3975.
Type
Article
Departments
Annotation
Bašić (2012) pointed to a gap in the proof of Corollary 5.10 in the paper On Brlek-Reutenauer conjecture of Balková et al. (2011) related to the Brlek-Reutenauer conjecture. In this corrigendum, we correct the proof and show that the corollary remains valid.

### Generalized Thue-Morse words and palindromic richness

Authors
Year
2012
Published
Kybernetika. 2012, 48(3), 361-370. ISSN 0023-5954.
Type
Article
Departments
Annotation
We prove that the generalized Thue-Morse word $\mathbf{t}_{b,m}$ defined for $b \geq 2$ and $m \geq 1$ as $\mathbf{t}_{b,m} = \left ( s_b(n) \mod m \right )_{n=0}^{+\infty}$, where $s_b(n)$ denotes the sum of digits in the base-$b$ representation of the integer $n$, has its language closed under all elements of a group $D_m$ isomorphic to the dihedral group of order $2m$ consisting of morphisms and antimorphisms. Considering simultaneously antimorphisms $\Theta \in D_m$, we show that $\mathbf{t}_{b,m}$ is saturated by $\Theta$-palindromes up to the highest possible level. Using the terminology generalizing the notion of palindromic richness for more antimorphisms recently introduced by the author and E. Pelantov'a, we show that $\mathbf{t}_{b,m}$ is $D_m$-rich. We also calculate the factor complexity of $\mathbf{t}_{b,m}$.

### Infinite words rich and almost rich in generalized palindromes

Authors
Pelantová, E.; Starosta, Š.
Year
2011
Published
Developments in Language Theory, 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011, Proceedings. Berlin: Springer-Verlag, 2011. pp. 406-416. Lecture Notes in Computer Science. ISSN 0302-9743. ISBN 978-3-642-22320-4.
Type
Proceedings paper
Departments
Annotation
We focus on $\Theta$-rich and almost $\Theta$-rich words over a finite alphabet $\mathcal{A}$, where $\Theta$ is an involutive antimorphism over $\mathcal{A}^*$. We show that any recurrent almost $\Theta$-rich word $\uu$ is an image of a recurrent \linebreak $\Theta'$-rich word under a suitable morphism, where $\Theta'$ is again an involutive antimorphism. Moreover, if the word $\uu$ is uniformly recurrent, we show that $\Theta'$ can be set to the reversal mapping. We also treat one special case of almost $\Theta$-rich words. We show that every $\Theta$-standard word with seed is an image of an Arnoux-Rauzy word.

### On Brlek-Reutenauer conjecture

Authors
Balková, L.; Pelantová, E.; Starosta, Š.
Year
2011
Published
Theoretical Computer Science. 2011, 412(41), 5649-5655. ISSN 0304-3975.
Type
Article
Departments
Annotation
Brlek and Reutenauer conjectured that any infinite word u with language closed under reversal satisfies the equality 2D(u) = Sigma(+infinity)(n=0) T(u)(n) in which D(u) denotes the defect of u and T(u)(n) denotes C(u)(n + 1) - C(u)(n) + 2 - P(u)(n + 1) - P(u)(n), where C(u) and P(u) are the factor and palindromic complexity of u, respectively. BrIek and Reutenauer verified their conjecture for periodic infinite words. Using their result, we prove the conjecture for uniformly recurrent words. Moreover, we summarize results and some open problems related to defects, which may be useful for the proof of the Brlek-Reutenauer conjecture in full generality.