Preimage problems for deterministic finite automata

Mikhail V. Berlinkov, Robert Ferens, Marek Szykuła

Given a subset of states $S$ of a deterministic finite automaton and a word $w$, the preimage is the subset of all states mapped to a state in $S$ by the action of $w$. We study th…