25 maja 2017 12:15
Seminarium ZZOiAA: Robert Ferens, Extending word problems for deterministic finite automata
Abstract: A word $w$ is \emph{extending} a subset of states $S$ of a deterministic finite automaton if the set of states mapped to $S$ by $w$ (the preimage of $S$ under the action of $w$) is larger than $S$.
This notion together with its variations has particular importance in the field of synchronizing automata, where a number of methods and algorithms rely on finding (short) extending words.
In this paper we study the complexity of several variants of extending word problems: deciding whether there exists an extending word, an extending word that extends to the whole set of states, a word avoiding a state, and a word that either extends or shrinks the subset.
Additionally, we study the complexity of these problems when an upper bound on the length of the word is also given, and we consider the subclasses of strongly connected, synchronizing, binary, and unary automata.
We show either hardness or polynomial algorithms for the considered variants.