22 citations · 75 across the 21 of their papers we have counts for
20 papers · 1 filter
Binary codes that do not preserve primitivity
Štěpán Holub, Martin Raška, Štěpán Starosta
A code is not primitivity preserving if there is a primitive list whose concatenation is imprimitive. We formalize a full characterization of su…
The Intersection of -Maximal Submonids
Giuseppa Castiglione, Štěpán Holub
Very little is known about the structure of the intersection of two -generated monoids of words, even for . Here we investigate the case of -maximal monoids, that is, mo…
Binary intersection formalized
Štěpán Holub, Štěpán Starosta
We provide a reformulation and a formalization of the classical result by Juhani Karhumäki characterizing intersections of two languages of the form . We u…
Pseudo-solutions of word equations
Štěpán Holub
We present a framework which allows a uniform approach to the recently introduced concept of pseudo-repetitions on words in the morphic case. This framework is at the same time mor…
Maximal State Complexity and Generalized de Bruijn Words
Daniel Gabric, Štěpán Holub, Jeffrey Shallit
We compute the exact maximum state complexity for the language consisting of words of length , and characterize languages achieving the maximum. We also consider a special c…
On the Height of Towers of Subsequences and Prefixes
Štěpán Holub, Tomáš Masopust, Michaël Thomazo
A tower is a sequence of words alternating between two languages in such a way that every word is a subsequence of the following word. The height of the tower is the number of word…
Prefix frequency of lost positions
Štěpán Holub
The concept of "lost positions" is a recently introduced tool for counting the number of runs in words. We investigate the frequency of lost positions in prefixes of words. This le…
Periods and borders of random words
Štěpán Holub, Jeffrey Shallit
We investigate the behavior of the periods and border lengths of random words over a fixed alphabet. We show that the asymptotic probability that a random word has a given maximal…
Fully bordered words
Štěpán Holub, Mike Müller
We characterize binary words that have exactly two unbordered conjugates and show that they can be expressed as a product of two palindromes.
Beyond the Runs Theorem
Johannes Fischer, Štěpán Holub, Tomohiro I +1
Recently, a short and elegant proof was presented showing that a binary word of length contains at most runs. Here we show, using the same technique and a computer search…
Equation in words
Jana Hadravová, Štěpán Holub
We will prove that the word is periodicity forcing if and , where and are positive integers. Also we will give examples showing that both…
Alternating Towers and Piecewise Testable Separators
Štěpán Holub, Tomáš Masopust, Michaël Thomazo
Two languages are separable by a piecewise testable language if and only if there exists no infinite tower between them. An infinite tower is an infinite sequence of strings altern…
On Upper and Lower Bounds on the Length of Alternating Towers
Štěpán Holub, Galina Jirásková, Tomáš Masopust
A tower between two regular languages is a sequence of strings such that all strings on odd positions belong to one of the languages, all strings on even positions belong to the ot…
Algebraic properties of word equations
Štěpán Holub, Jan Žemlička
The question about maximal size of independent system of word equations is one of the most striking problems in combinatorics on words. Recently, Aleksi Saarela has introduced a ne…
Words with unbounded periodicity complexity
Štěpán Holub
If an infinite non-periodic word is uniformly recurrent or is of bounded repetition, then the limit of its periodicity complexity is infinity. Moreover, there are uniformly recurre…
On an algorithm for multiperiodic words
Štěpán Holub
We consider an algorithm by Tijdeman and Zamboni constructing a word of a given length that has a given set of periods, and the richest possible alphabet. We show that this algorit…
Binary equality sets are generated by two words
Štěpán Holub
We show that the equality language of two non-periodic binary morphisms is generated by at most two words. If its rank is two, then the generators start (and end) with different le…
Complexity of testing morphic primitivity
Vojtěch Matocha, Štěpán Holub
We analyze the algorithm in [Holub, 2009], which decides whether a given word is a fixed point of a nontrivial morphism. We show that it can be implemented to have complexity in O(…
Abelian powers in paper-folding words
Štěpán Holub
We show that paper folding words contain arbitrarily large abelian powers.
Proceedings 8th International Conference Words 2011
Petr Ambrož, Štěpán Holub, Zuzana Masáková
WORDS is the main international event in Combinatorics on Words. It is a biannual conference devoted to research of words (i.e., finite or infinite sequences of symbols over a fini…