30 citations · 111 across the 34 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
cs.FL2022
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…
cs.FL2022
An Improved Algorithm for Finding the Shortest Synchronizing Words
Marek Szykuła, Adam Zyzik
A synchronizing word of a deterministic finite complete automaton is a word whose action maps every state to a single one. Finding a shortest or a short synchronizing word is a cen…