Reset Complexity of Ideal Languages Over a Binary Alphabet
Marina Maslennikova · International Journal of Foundations of Computer Science · 2019
We prove PSPACE-completeness of checking whether a given ideal language serves as the language of reset words for some automaton with at most four states over a binary alphabet. We compare the reset complexity and the state complexity for languages related to slowly synchronizing automata.