6 citations · 6 across the 3 of their papers we have counts for
4 papers · 1 filter
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…
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…
Preimage problems for deterministic finite automata
Mikhail V. Berlinkov, Robert Ferens, Marek Szykuła
Given a subset of states of a deterministic finite automaton and a word , the preimage is the subset of all states mapped to a state in by the action of . We study th…
Complexity of regular bifix-free languages
Robert Ferens, Marek Szykuła
We study descriptive complexity properties of the class of regular bifix-free languages, which is the intersection of prefix-free and suffix-free regular languages. We show that th…