Source author record

Štěpán Starosta

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Artificial Intelligence Formal Languages and Automata Theory Logic in Computer Science

Catalog footprint

Research overview

11works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Producing symmetrical facts for lists induced by the list reversal mapping in Isabelle/HOL

Many facts possess symmetrical counterparts that often require a separate formal proof, depending on the nature of the involved symmetry. We introduce a method in Isabelle/HOL which produces such a symmetrical fact for the list datatype and the symmetry induced by the list reversal mapping. The method is implemented as an attribute and its result is based on user-declared symmetry rules. Besides general rules, we provide rules that are aimed to be applied in the domain of Combinatorics on Words.

preprint2020arXiv

Binary intersection formalized

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.

preprint2016arXiv

Exchange of three intervals: itineraries, substitutions and palindromicity

Given a symmetric exchange of three intervals, we provide a detailed description of the return times to a subinterval and the corresponding itineraries. We apply our results to morphisms fixing words coding non-degenerate three interval exchange transformation. This allows us to prove that the conjecture stated by Hof, Knill and Simon is valid for such infinite words.

preprint2014arXiv

Morphic images of episturmian words having finite palindromic defect

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 (resp. zero) palindromic defect. They also enable us to construct new examples of binary $H$ -rich and almost $H$ -rich words, where $H = \{\rm{Id}, R, E, RE \}$ is the group generated by both involutory antimorphisms on a binary alphabet.

preprint2013arXiv

Characterization of circular D0L systems

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 here a complete proof. Further, employing our previous result, we give a simple algorithm to test circularity of an injective D0L system.

preprint2013arXiv

Palindromic closures using multiple antimorphisms

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.

preprint2013arXiv

Palindromic richness for languages invariant under more symmetries

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 $Θ(w) = w$ for some antimorphism $Θ\in G$ . We give several equivalent descriptions which are generalizations of know characterizations of rich words (in the terms of classical palindromes) and show two examples of $G$ -rich words.

preprint2012arXiv

Languages invariant under more symmetries: overlapping factors versus palindromic richness

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 $n\in \mathbb{N}$ \,. Word for which the equality is attained for any $n$ is usually called rich in palindromes. In this article 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 notion of $G$ -palindromic richness and give several examples of $G$ -rich words, including the Thue-Morse sequence as well.

preprint2011arXiv

Generalized Thue-Morse words and palindromic richness

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} = (s_b(n) \mod m)_{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 $Θ\in D_m$ , we show that $\mathbf{t}_{b,m}$ is saturated by $Θ$ -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á, we show that $\mathbf{t}_{b,m}$ is $D_m$ -rich. We also calculate the factor complexity of $\mathbf{t}_{b,m}$ .

preprint2011arXiv

Infinite words rich and almost rich in generalized palindromes

We focus on $Θ$ -rich and almost $Θ$ -rich words over a finite alphabet $\mathcal{A}$ , where $Θ$ is an involutive antimorphism over $\mathcal{A}^*$ . We show that any recurrent almost $Θ$ -rich word $\uu$ is an image of a recurrent $Θ'$ -rich word under a suitable morphism, where $Θ'$ is again an involutive antimorphism. Moreover, if the word $\uu$ is uniformly recurrent, we show that $Θ'$ can be set to the reversal mapping. We also treat one special case of almost $Θ$ -rich words. We show that every $Θ$ -standard words with seed is an image of an Arnoux-Rauzy word.

preprint2011arXiv

Infinite Words with Finite Defect

In this paper, we provide a new characterization of uniformly recurrent words with finite defect based on a relation between the palindromic and factor complexity. Furthermore, we introduce a class of morphisms P_ret closed under composition and we show that a uniformly recurrent word with finite defect is an image of a rich (also called full) word under a morphism of class P_ret. This class is closely related to the well-known class P defined by Hof, Knill, and Simon; every morphism from P_ret is conjugate to a morphism of class P.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Štěpán Starosta

Research overview

Is this your work?

11 publications

Producing symmetrical facts for lists induced by the list reversal mapping in Isabelle/HOL

Binary intersection formalized

Exchange of three intervals: itineraries, substitutions and palindromicity

Morphic images of episturmian words having finite palindromic defect

Characterization of circular D0L systems

Palindromic closures using multiple antimorphisms

Palindromic richness for languages invariant under more symmetries

Languages invariant under more symmetries: overlapping factors versus palindromic richness

Generalized Thue-Morse words and palindromic richness

Infinite words rich and almost rich in generalized palindromes

Infinite Words with Finite Defect

See the researcher in context

Building this map preview