VLDB 2026 Research / reviewers in the wild / expert
Vojtech Vorel
dblp:140/9811
· DBLP profile ↗
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
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2021 | Lower Bounds on Avoiding ThresholdsabstractFor 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 |
MFCS | 3 |
| 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 |
SAT | 3 |
| 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 |
DLT | 2 |
| 2015 | Complexity of Road Coloring with Prescribed Reset Words
Vojtech Vorel, Adam Roman |
LATA | 1 |
| 2014 | Complexity of a Problem Concerning Reset Words for Eulerian Binary Automata
Vojtech Vorel |
LATA | 1 |