4 citations · 5 across the 3 of their papers we have counts for
4 papers · 1 filter
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…