Zobrazeno 1 - 10
of 55
pro vyhledávání: '"Vorel, Vojtěch"'
Publikováno v:
Theoretical Computer Science, Volume 762, 2019, pp. 51-73
Constraint "at most one" is a basic cardinality constraint which requires that at most one of its $n$ boolean inputs is set to $1$. This constraint is widely used when translating a problem into a conjunctive normal form (CNF) and we investigate its
Externí odkaz:
http://arxiv.org/abs/1704.08934
Autor:
Szykuła, Marek, Vorel, Vojtěch
Publikováno v:
Developments in Language Theory (DLT 2016), volume 9840 of LNCS, pages 380--392, 2016
We present an infinite series of $n$-state Eulerian automata whose reset words have length at least $(n^2-3)/2$. This improves the current lower bound on the length of shortest reset words in Eulerian automata. We conjecture that $(n^2-3)/2$ also for
Externí odkaz:
http://arxiv.org/abs/1604.02879
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 class of languages in terms of special shuffle expressions and survey o
Externí odkaz:
http://arxiv.org/abs/1512.00482
Autor:
Vorel, Vojtěch
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 close the study raised by \v{C}erno and Mr\'{a}z in 2010 by proving that
Externí odkaz:
http://arxiv.org/abs/1511.08642
Autor:
Vorel, Vojtěch
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 properties are solved. Besides this, we correct erroneous results presented in
Externí odkaz:
http://arxiv.org/abs/1511.08396
Autor:
Vorel, Vojtěch, Roman, Adam
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 reset word. There may also be a need for a particular reset word to be
Externí odkaz:
http://arxiv.org/abs/1412.0799
Autor:
Vorel, Vojtěch
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 given maximum length for a given automaton is known to be an NP-complet
Externí odkaz:
http://arxiv.org/abs/1409.2003
Autor:
Vorel, Vojtěch, Roman, Adam
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, parameterized by the number of states, does not admit a polynomial kern
Externí odkaz:
http://arxiv.org/abs/1403.4749
Autor:
Vorel, Vojtěch
We present a strongly exponential lower bound that applies both to the subset synchronization threshold for binary deterministic automata and to the careful synchronization threshold for binary partial automata. In the later form, the result finishes
Externí odkaz:
http://arxiv.org/abs/1403.3972
Autor:
Vorel, Vojtěch, Roman, Adam
Publikováno v:
In Journal of Computer and System Sciences September 2019 104:342-358
