25 citations · 47 across the 12 of their papers we have counts for
4 papers · 1 filter
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…
Complexity of Universality and Related Problems for Partially Ordered NFAs
Markus Krötzsch, Tomáš Masopust, Michaël Thomazo
Partially ordered nondeterminsitic finite automata (poNFAs) are NFAs whose transition relation induces a partial order on states, that is, for which cycles occur only in the form o…
On -piecewise testability (preliminary report)
Tomáš Masopust, Michaël Thomazo
For a non-negative integer , a language is -piecewise test\-able (-PT) if it is a finite boolean combination of languages of the form for…
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…