  The constrained synchronization problem (CSP) asks for a synchronizing word
of a given input automaton contained in a regular set of constraints. It could
be viewed as a special case of synchronization of a discrete event system under
supervisory control. Here, we study the computational complexity of this
problem for the class of sparse regular constraint languages. We give a new
characterization of sparse regular sets, which equal the bounded regular sets,
and derive a full classification of the computational complexity of CSP for
letter-bounded regular constraint languages, which properly contain the
strictly bounded regular languages. Then, we introduce strongly
self-synchronizing codes and investigate CSP for bounded languages induced by
these codes. With our previous result, we deduce a full classification for
these languages as well. In both cases, depending on the constraint language,
our problem becomes NP-complete or polynomial time solvable.

Formal Languages and Automata Theory;Computational Complexity;Systems and Control;Systems and Control