Extensions to Minimal Synchronizing Words
Henning Fernau, Stefan Hoffmann · Journal of automata, languages and combinatorics · 2019
Extension problems have been studied for a variety of combinatorial properties, but not so for combinatorial questions on formal languages. We will raise this type of question for one of the undoubtedly most prominent properties of words in relation to finite automata, namely their synchronizability. In contrast to other areas of discrete mathematics, say, to graph theory, there are several natural ways how to define extension problems for synchronizing words, depending on the chosen partial order on the set of all words. Some variants lead to polynomial-time solvable extension problems, while others yield (co-)NP-hard extension problems, and still others lead to open problems. We also take a closer look at commutative automata and show that the combinatorics of synchronizing words is much easier for this class, while the related computability problems are still NP-hard.