Ideal Separation and General Theorems for Constrained Synchronization and their Application to Small Constraint Automata
arXiv:2005.05907
Abstract
In the constrained synchronization problem we ask if a given automaton admits a synchronizing word coming from a fixed regular constraint language. We show that intersecting a given constraint language with an ideal language decreases the computational complexity. Additionally, we state a theorem giving PSPACE-hardness that broadly generalizes previously used constructions and a result on how to combine languages by concatenation to get polynomial time solvable constrained synchronization problems. We use these results to give a classification of the complexity landscape for small constraint automata of up to three states.
Complete reworking of the 1st version. The classification of the 1st version is achieved by identifying and utilising more general theorems, which are also stated in the work