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

Proceedings paper

10.1007/978-3-031-10769-6_23

Department of Applied Mathematics

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).

Article

10.1016/j.ejc.2021.103318

Department of Applied Mathematics

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.

Article

10.1016/j.tcs.2021.03.002

Department of Applied Mathematics

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.

Article

Department of Applied Mathematics

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).

Proceedings paper

10.4230/LIPIcs.ITP.2021.22

Department of Applied Mathematics

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.

Article

Department of Applied Mathematics

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.

Article

Department of Applied Mathematics

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).

Proceedings paper

10.1007/978-3-030-81508-0_18

Department of Applied Mathematics

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.

Article

10.1016/J.TCS.2021.03.033

Department of Applied Mathematics

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.

Article

10.1016/j.jnt.2019.10.027

Department of Applied Mathematics

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.

Article

10.1016/j.tcs.2019.04.021

Department of Applied Mathematics

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.

Proceedings paper

10.1007/978-3-030-28796-2_18

Department of Applied Mathematics

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.

Article

10.1016/j.tcs.2018.06.037

Department of Applied Mathematics

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.

Article

10.1016/j.ejc.2017.01.003

Department of Applied Mathematics

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.

Article

10.1016/j.ejc.2016.12.006

Department of Applied Mathematics

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.

Proceedings paper

10.1007/978-3-319-66396-8_7

Department of Applied Mathematics

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.

Article

Department of Applied Mathematics

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.

Article

10.14311/AP.2016.56.0462

Department of Applied Mathematics

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.

Article

10.1088/1751-8113/49/15/155201

Department of Applied Mathematics

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.

Article

10.1016/j.ejc.2015.07.001

Department of Applied Mathematics

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.

Article

10.1016/j.jda.2015.03.006

Department of Applied Mathematics

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.

Proceedings paper

Department of Applied Mathematics

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.

Proceedings paper

10.1007/978-3-319-21500-6_30

Department of Applied Mathematics

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.

Article

10.3934/dcds.2015.35.3483

Department of Applied Mathematics

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.

Article

Department of Applied Mathematics

We present basic usage of open computer algebra system SageMath and we discuss the need of openness of mathematical software.

Article

10.1016/j.tcs.2014.03.020

Department of Applied Mathematics

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.

Article

10.1016/j.tcs.2013.07.021

Department of Applied Mathematics

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.

Article

10.1016/j.disc.2013.07.002

Department of Theoretical Computer Science

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.

Article

10.1016/j.tcs.2012.12.024

Department of Applied Mathematics

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.

Book chapter

10.1007/978-0-8176-8400-6_1

Department of Applied Mathematics

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.

Article

10.1142/S012905411240045X

Department of Applied Mathematics

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.

Article

10.1016/j.tcs.2012.09.003

Department of Applied Mathematics

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.

Article

Department of Theoretical Computer Science

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}$.

Proceedings paper

Department of Theoretical Computer Science

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.

Article

10.1016/j.tcs.2011.06.031

Department of Theoretical Computer Science

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.