  We investigate the constrained synchronization problem for weakly acyclic, or
partially ordered, input automata. We show that, for input automata of this
type, the problem is always in NP. Furthermore, we give a full classification
of the realizable complexities for constraint automata with at most two states
and over a ternary alphabet. We find that most constrained problems that are
PSPACE-complete in general become NP-complete. However, there also exist
constrained problems that are PSPACE-complete in the general setting but become
polynomial time solvable when considered for weakly acyclic input automata. We
also investigate two problems related to subset synchronization, namely if
there exists a word mapping all states into a given target subset of states,
and if there exists a word mapping one subset into another. Both problems are
PSPACE-complete in general, but in our setting the former is polynomial time
solvable and the latter is NP-complete.
