Ideal Separation and General Theorems for Constrained Synchronization and Their Application to Small Constraint Automata

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 does not increase 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.