Title: Subset Synchronization in Monotonic Automata,
Abstract: We study extremal and algorithmic questions of subset and careful
synchronization in monotonic automata. We show that several synchronization
problems that are hard in general automata can be solved in polynomial time in
monotonic automata, even without knowing a linear order of the states preserved
by the transitions. We provide asymptotically tight bounds on the maximum
length of a shortest word synchronizing a subset of states in a monotonic
automaton and a shortest word carefully synchronizing a partial monotonic
automaton. We provide a complexity framework for dealing with problems for
monotonic weakly acyclic automata over a three-letter alphabet, and use it to
prove NP-completeness and inapproximability of problems such as {\sc Finite
Automata Intersection} and the problem of computing the rank of a subset of
states in this class. We also show that checking whether a monotonic partial
automaton over a four-letter alphabet is carefully synchronizing is NP-hard.
Finally, we give a simple necessary and sufficient condition when a strongly
connected digraph with a selected subset of vertices can be transformed into a
deterministic automaton where the corresponding subset of states is
synchronizing.