6 citations · 6 across the 3 of their papers we have counts for
5 papers
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…
Solving one variable word equations in the free group in cubic time
Robert Ferens, Artur Jeż
A word equation with one variable in a free group is given as , where both and are words over the alphabet of generators of the free group and , for a fix…
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…