4 citations · 5 across the 3 of their papers we have counts for
8 papers · 1 filter
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…
Complexity of a Problem Concerning Reset Words for Eulerian Binary Automata
Vojtěch Vorel
A word is called a reset word for a deterministic finite automaton if it maps all the states of the automaton to a unique state. Deciding about the existence of a reset word of a g…
Parameterized Complexity of Synchronization and Road Coloring
Vojtěch Vorel, Adam Roman
First, we close the multivariate analysis of a canonical problem concerning short reset words (SYN), as it was started by Fernau et al. (2013). Namely, we prove that the problem, p…
Subset Synchronization and Careful Synchronization of Binary Finite Automata
Vojtěch Vorel
We present a strongly exponential lower bound that applies both to the subset synchronization threshold for binary deterministic automata and to the careful synchronization thresho…