activity
20142017
most citedAn Extremal Series of Eulerian Synchronizing Automata

4 citations · 5 across the 3 of their papers we have counts for

collaborators
Showing cs.FLShow all

8 papers · 1 filter

cs.FL2016★ 4 cited

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…

cs.FL2015

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…

cs.FL2015

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…

cs.FL2015

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…

cs.FL2014

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…

cs.FL2014★ 1 cited

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…

cs.FL2014

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…

cs.FL2014

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…