

\section{Introduction}
\label{sec:introduction}


\input{introduction}

\section{Preliminaries}
\label{sec:preliminaries}

\input{preliminaries}



\section{Constrained Synchronization of Weakly Acyclic Automata}

\input{constr_sync_waa}


\section{Subset Synchronization Problems}

\input{subset_sync_problems}

\section{Constraint Automata with Two States and at most Three Letters}

\input{two_states}

\section{Relation to Automata with TTSPL Automaton Graphs}

\input{ttspl}

\section{Conclusion}

We have investigated the complexity of the constrained synchronization
problem for weakly acyclic input automata. We noticed that in this setting, the problem
is always in $\textsf{NP}$. In the general setting, it was possible to have $\textsf{PSPACE}$-complete constrained 
problems, whereas this is no longer possibly in our setting. 
We have investigated the complexities for small constrained automata in the same way as
done in the general case in~\cite{DBLP:conf/mfcs/FernauGHHVW19}.
We found out that certain problems that are $\textsf{PSPACE}$-complete in general
become $\textsf{NP}$-complete, whereas others that are $\textsf{PSPACE}$-complete even become polynomial time solvable.
A similar phenomenon was observed for certain subset synchronization problems
that are all $\textsf{PSPACE}$-complete in general.

It is natural to continue this investigation for other classes of automata, to find out what
properties are exactly needed to realize $\textsf{PSPACE}$-complete problems or for what other
classes we only have $\textsf{NP}$-complete constrained problems, or what are the minimum requirements
on the input automata to realize $\textsf{NP}$-complete problems.

Also, a complete classification of all possible realizable complexities, a problem orginally posed in~\cite{DBLP:conf/mfcs/FernauGHHVW19}, is still open. Hence, as a first step it would be interesting
to know if for our restricted problem only the complexities $\textsf{P}$
and $\textsf{NP}$-complete arise, or if we can realize a constrained problem equivalent
to some $\textsf{NP}$-intermediate candidate problem.

\smallskip \noindent \footnotesize
\textbf{Acknowledgement.} I thank the anonymous reviewers for noticing some issues
in the proofs of Theorem~\ref{thm:set_transporter_weakly_acyclic} and Proposition~\ref{prop:np_complete_cases} that have been fixed. Also, I thank them for pointing out typos and some unclear formulations.

\bibliographystyle{splncs04}


\section{Monotonic Constraint Automata with Three States and Arbitrary Alphabet}


\subsection{Totally Ordered}

\begin{proposition}
 If $|\Sigma_{1,1}| \ge 2$, then pspace hard
\end{proposition}
\begin{proof}
 Let $a,b \in \Sigma_{1,1}$ be distinct and $c \in \Sigma_{1,2}$
 and $d \in \Sigma_{2,3}$.

 Then, note that $c \notin \Sigma_{1,1}$, we have $\Sigma^*acd\Sigma^* \cap L(\mathcal B) = \Sigma_{1,1}^*acd\Sigma_{3,3}^*$.
 
 
 
 
\end{proof}


\begin{proposition}
 If $|\Sigma_{2,2}| \ge 2$, then pspace hard
\end{proposition}
\begin{proof}

 %

 %

\end{proof}





