Search

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-complete problem. We prove that it remains NP-complete even if restricted to Eulerian automata with binary alphabets, as it has been conjectured by Martyugin (2011)., Extended version of a paper presented at LATA 2014

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 admitted. For certain words it is NP-complete to decide whether there is a suitable coloring of a given multigraph. We present a classification of all words over the binary alphabet that separates such words from those that make the problem solvable in polynomial time. We show that the classification becomes different if we consider only strongly connected multigraphs. In this restricted setting the classification remains incomplete., Comment: To be presented at LATA 2015

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 CNF encodings suitable for this purpose. An encoding differs from a CNF representation of a function in that it can use auxiliary variables. We are especially interested in propagation complete encodings which have the property that unit propagation is strong enough to enforce consistency on input variables. We show a lower bound on the number of clauses in any propagation complete encoding of the "at most one" constraint. The lower bound almost matches the size of the best known encodings. We also study an important case of 2-CNF encodings where we show a slightly better lower bound. The lower bound holds also for a related "exactly one" constraint., 38 pages, version 3 is significantly reorganized in order to improve readability

First, we show that universality, regularity, and related properties of general jumping finite automata are undecidable, which answers questions asked by Meduna and Zemek in 2012. Second, we close a study started by \v{C}erno and Mr\'{a}z in 2010 by proving that a clearing restarting automaton using contexts of length two can accept a binary non-context-free language., Journal of Automata, Languages and Combinatorics, Volume 22, Numbers 1-3, 2017, 189-203

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 forms an upper bound for this class and we experimentally verify it for small automata by an exhaustive computation.

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 other equivalent notions from the existing literature. Moreover, we present several results concerning computational hardness and algorithms for parsing and other basic tasks concerning jumping finite automata.

We complete the initial study of jumping finite automata, which was started in a former article of Meduna and Zemek [7]. The open questions about basic closure properties are solved. Besides this, we correct erroneous results presented in the article. Finally, we point out important relations between jumping finite automata and some other models studied in the literature.

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 the research initiated by Martyugin (2013). Moreover, we show that both the thresholds remain strongly exponential even if restricted to strongly connected binary automata. In addition, we apply our methods to computational complexity. Existence of a subset reset word is known to be PSPACE-complete; we show that this holds even under the restriction to strongly connected binary automata. The results apply also to the corresponding thresholds in two more general settings: D1- and D3-directable nondeterministic automata and composition sequences over finite domains., An extended version of the paper "Subset Synchronization of Transitive Automata" presented at AFL 2014

A word is called a reset word for a deterministic finite automaton if it maps all states of the automaton to one state. Deciding about the existence of a reset word of given length for a given automaton is known to be a NP-complete problem. We prove that it remains NP-complete even if restricted on Eulerian automata over the binary alphabet, as it has been conjectured by Martyugin 2011.