Constrained synchronization and commutativity

In the constrained synchronization problem we want to know if a given input automaton admits a synchronizing word contained in a (fixed) regular constraint language. Here we study the computational complexity of the constrained synchronization problem for the class of regular commutative constraint languages and the computational complexity of the problem restricted to commutative input semi-automata. We give a full classification of the computational complexity of the constrained synchronization problem for commutative regular constraints. Depending on the constraint language, our problem becomes PSPACE-complete, NP-complete or polynomial time solvable. In addition, we derive a polynomial time decision procedure for the complexity of the constrained synchronization problem, given a constraint automaton accepting a commutative language as input. Furthermore, for commutative input semi-automata, the problem is decidable in polynomial time, regardless of the regular constraint language.

Authors

• Stefan Hoffmann

Keywords

• Constrained synchronization
• Computational complexity
• Automata theory
• Commutative language