Constraint Synchronization with Two or Three State Partial Constraint Automata
share
Here, we study the question if synchronizing words exist that belong to some fixed constraint language, given by some partial finite automaton called constraint automaton. We strengthen a previous result by giving a complete classification of the computational complexity landscape for constraint automata with two states and an arbitrary alphabet. We also give a classification for three state automata with a binary alphabet, for the class of automata such that the initial state is connected with at most one other state. Among them, we find constraint automata with three states and a binary alphabet, for which the problem is PSPACE-complete. We conclude that, for a binary alphabet, we need at least three states to realise PSPACE-hard problems. As it turns out, the three state constraint automata for which the problem is NP-complete are quite rare. To derive our results, we generalize the known polynomial time algorithm from the unconstrained setting to broaden the range of constraint problems that could be solved in PTIME.
READ FULL TEXT