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

Proděkan pro vědu a výzkum

Publikace

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

Autoři
Starosta, Š.; Řada, H.
Rok
2020
Publikováno
Journal of Number Theory. 2020, 212 122-172. ISSN 0022-314X.
Typ
Článek
Anotace
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

Rok
2019
Publikováno
Theoretical Computer Science. 2019, 790 131-137. ISSN 0304-3975.
Typ
Článek
Anotace
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

Rok
2019
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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

Autoři
Klouda, K.; Starosta, Š.; Medková, K.; Pelantová, E.
Rok
2018
Publikováno
Theoretical Computer Science. 2018, 743 23-37. ISSN 0304-3975.
Typ
Článek
Anotace
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

Autoři
Starosta, Š.; Masáková, Z.; Pelantová, E.
Rok
2017
Publikováno
European Journal of Combinatorics. 2017, 62 217-231. ISSN 0195-6698.
Typ
Článek
Anotace
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

Autoři
Starosta, Š.; Labbé, S.; Pelantová, E.
Rok
2017
Publikováno
European Journal of Combinatorics. 2017, 62 132-146. ISSN 0195-6698.
Typ
Článek
Anotace
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

Autoři
Starosta, Š.; Pelantová, E.
Rok
2017
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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

Autoři
Starosta, Š.; Pelantová, E.
Rok
2016
Publikováno
Discrete Mathematics and Theoretical Computer Science. 2016, 18(3), 1-26. ISSN 1462-7264.
Typ
Článek
Anotace
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

Autoři
Starosta, Š.; Masáková, Z.; Pelantová, E.
Rok
2016
Publikováno
Acta Polytechnica. 2016, 56(6), 462-471. ISSN 1805-2363.
Typ
Článek
Anotace
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

Autoři
Starosta, Š.; Pelantová, E.; Znojil, Miloslav
Rok
2016
Publikováno
Journal of Physics A: Mathematical and Theoretical. 2016, 49(15), 1-19. ISSN 1751-8113.
Typ
Článek
Anotace
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

Autoři
Rok
2016
Publikováno
European Journal of Combinatorics. 2016, 51 359-371. ISSN 0195-6698.
Typ
Článek
Anotace
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

Rok
2015
Publikováno
Journal of Discrete Algorithms. 2015, 33 130-138. ISSN 1570-8667.
Typ
Článek
Anotace
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

Autoři
Starosta, Š.; Veselý, V.
Rok
2015
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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

Autoři
Starosta, Š.; Masáková, Z.; Pelantová, E.
Rok
2015
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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

Autoři
Starosta, Š.; Kupsa, M.
Rok
2015
Publikováno
Discrete and Continuous Dynamical Systems - Series A. 2015, 35(8), 3483-3501. ISSN 1078-0947.
Typ
Článek
Anotace
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.

Počítáme otevřeně se SageMath

Rok
2015
Publikováno
Pokroky matematiky, fyziky a astronomie. 2015, 60(4), 300-313. ISSN 0032-2423.
Typ
Článek
Anotace
Prezentujeme základní použití otevřeného počítačového algebraického systému SageMath a zamýšlíme se nad významem otevřenosti matematického software.

Palindromic closures using multiple antimorphisms

Autoři
Starosta, Š.; Pelantová, E.; Jajcayová, T.
Rok
2014
Publikováno
Theoretical Computer Science. 2014, 533 37-45. ISSN 0304-3975.
Typ
Článek
Anotace
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

Autoři
Starosta, Š.; Pelantová, E.
Rok
2014
Publikováno
Theoretical Computer Science. 2014, 518 42-63. ISSN 0304-3975.
Typ
Článek
Anotace
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

Autoři
Starosta, Š.; Pelantová, E.
Rok
2013
Publikováno
Discrete Mathematics. 2013, 313(21), 2432-2445. ISSN 0012-365X.
Typ
Článek
Anotace
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

Autoři
Starosta, Š.; Balková, L.; Pelantová, E.
Rok
2013
Publikováno
Theoretical Computer Science. 2013, 475 120-125. ISSN 0304-3975.
Typ
Článek
Anotace
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

Autoři
Starosta, Š.; Arnoux, P.
Rok
2013
Publikováno
Further Developments in Fractals and Related Fields. Boston: Birkhaeuser, 2013. p. 1-23. Trends in Mathematics. ISBN 978-0-8176-8399-3.
Typ
Kapitola v knize
Anotace
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

Autoři
Starosta, Š.; Pelantová, E.
Rok
2012
Publikováno
International Journal of Foundations of Computer Science. 2012, 23(5), 1067-1083. ISSN 0129-0541.
Typ
Článek
Anotace
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"

Autoři
Starosta, Š.; Balková, L.; Pelantová, E.
Rok
2012
Publikováno
Theoretical Computer Science. 2012, 465 73-74. ISSN 0304-3975.
Typ
Článek
Anotace
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

Autoři
Rok
2012
Publikováno
Kybernetika. 2012, 48(3), 361-370. ISSN 0023-5954.
Typ
Článek
Anotace
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

Autoři
Starosta, Š.; Pelantová, E.
Rok
2011
Publikováno
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.
Typ
Stať ve sborníku
Anotace
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

Autoři
Starosta, Š.; Balková, L.; Pelantová, E.
Rok
2011
Publikováno
Theoretical Computer Science. 2011, 412(41), 5649-5655. ISSN 0304-3975.
Typ
Článek
Anotace
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.