4 citations · 5 across the 3 of their papers we have counts for
9 papers
A lower bound on CNF encodings of the at-most-one constraint
Petr Kučera, Petr Savický, Vojtěch Vorel
Constraint "at most one" is a basic cardinality constraint which requires that at most one of its boolean inputs is set to . This constraint is widely used when translating…
An Extremal Series of Eulerian Synchronizing Automata
Marek Szykuła, Vojtěch Vorel
We present an infinite series of -state Eulerian automata whose reset words have length at least . This improves the current lower bound on the length of shortest res…
On Basic Properties of Jumping Finite Automata
Vojtěch Vorel
We complete the initial study of jumping finite automata, which was started in a former article of Meduna and Zemek \citep{athMED1}. The open questions about basic closure properti…
Characterization and Complexity Results on Jumping Finite Automata
Henning Fernau, Meenakshi Paramasivan, Markus L. Schmid +1
In a jumping finite automaton, the input head can jump to an arbitrary position within the remaining input after reading and consuming a symbol. We characterize the corresponding c…
Two Results on Discontinuous Input Processing
Vojtěch Vorel
First, we show that universality and other properties of general jumping finite automata are undecidable, which answers a question asked by Meduna and Zemek in 2012. Second, we clo…
Complexity of Road Coloring with Prescribed Reset Words
Vojtěch Vorel, Adam Roman
By the Road Coloring Theorem (Trahtman, 2008), the edges of any aperiodic directed multigraph with a constant out-degree can be colored such that the resulting automaton admits a r…