4 papers
Synchronization of strongly connected partial DFAs and prefix codes
Mikhail V. Berlinkov, Robert Ferens, Andrew Ryzhikov +1
We study synchronizing partial DFAs, which extend the classical concept of synchronizing complete DFAs and are a special case of synchronizing unambiguous NFAs. A partial DFA is ca…
Regular Games -- an Automata-Based General Game Playing Language
RadosÅaw Miernik, Marek SzykuÅa, Jakub Kowalski +3
We propose a new General Game Playing (GGP) system called Regular Games (RG). The main goal of RG is to be both computationally efficient and convenient for game design. The system…
Reset thresholds of transformation monoids
Igor Rystsov, Marek SzykuÅa
Motivated by the Äerný conjecture for automata, we introduce the concept of monoidal automata, which allows the formulation of the Äerný conjecture for monoids. We show upper b…
Completely reachable automata: a quadratic decision algorithm and a quadratic upper bound on the reaching threshold
Robert Ferens, Marek SzykuÅa
A complete deterministic finite (semi)automaton (DFA) with a set of states is \emph{completely reachable} if every nonempty subset of is the image of the action of some wor…