Vojtech Vorel

dblp:140/9811 · DBLP profile ↗
← Back
9ranked-venue papers
4as first author
1since 2021 · last 2021
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 9 · 4 first-author · 1 since 2021Artificial intelligence and machine learning · 1
YearPublicationVenuePosition
2021 Lower Bounds on Avoiding Thresholds
abstract
For a DFA, a word avoids a subset of states, if after reading that word the automaton cannot be in any state from the subset regardless of its initial state. A subset that admits an avoiding word is avoidable. The k-avoiding threshold of a DFA is the smallest number such that every avoidable subset of size k can be avoided with a word no longer than that number. We study the problem of determining the maximum possible k-avoiding thresholds. For every fixed k ≥ 1, we show a general construction of strongly connected DFAs with n states and the k-avoiding threshold in Θ(n^k). This meets the known upper bound for k ≥ 3. For k = 1 and k = 2, the known upper bounds are respectively in 𝒪(n²) and in 𝒪(n³). For k = 1, we show that 2n-3 is attainable for every number of states n in the class of strongly connected synchronizing binary DFAs, which is supposed to be the best possible in the class of all DFAs for n ≥ 8. For k = 2, we show that the conjectured solution for k = 1 (an upper bound in 𝒪(n)) also implies a tight upper bound in 𝒪(n²) on 2-avoiding threshold. Finally, we discuss the possibility of using k-avoiding thresholds of synchronizing automata to improve upper bounds on the length of the shortest reset words.
Robert Ferens, Marek Szykula, Vojtech Vorel
MFCS3
2019 Complexity of road coloring with prescribed reset words
Vojtech Vorel, Adam Roman
J. Comput. Syst. Sci.1
2019 A lower bound on CNF encodings of the at-most-one constraint
Petr Kucera, Petr Savický, Vojtech Vorel
Theor. Comput. Sci.3
2017 A Lower Bound on CNF Encodings of the At-Most-One Constraint
Petr Kucera, Petr Savický, Vojtech Vorel
SAT3
2017 Complexity of a problem concerning reset words for Eulerian binary automata
Vojtech Vorel
Inf. Comput.1
2017 Characterization and complexity results on jumping finite automata
Henning Fernau, Meenakshi Paramasivan, Markus L. Schmid, Vojtech Vorel
Theor. Comput. Sci.4
2016 An Extremal Series of Eulerian Synchronizing Automata
Marek Szykula, Vojtech Vorel
DLT2
2015 Complexity of Road Coloring with Prescribed Reset Words
Vojtech Vorel, Adam Roman
LATA1
2014 Complexity of a Problem Concerning Reset Words for Eulerian Binary Automata
Vojtech Vorel
LATA1