Title: Constrained Synchronization for Monotonic and Solvable Automata and Automata with Simple Idempotents
Abstract: For general input automata, there exist regular constraint languages such that asking if a given input automaton admits a synchronizing word in the constraint language is PSPACE-complete or NP-complete. Here, we investigate this problem for the following classes of input automata: monotonic automata, solvable automata and automata with simple idempotents over a binary alphabet. The latter class contains, for example, the Černý family of automata, an infinite family of n-state automata whose shortest synchronizing words have length $$(n-1)^2$$ . Solvable automata generalize both commutative automata and weakly acyclic automata. We find that for monotonic automata, the problem is solvable in nondeterministic logarithmic space, for every regular constraint language. We identify a subclass of solvable automata for which the problem is in NP. This subclass strictly contains the weakly acyclic automata. In the course of our investigation we derive a sharp linear upper bound for the length of a shortest synchronizing word in a given constraint language, improving previous quadratic bounds for weakly acyclic and commutative automata. We also give structural characterizations of solvable automata and their recognized languages that imply that they recognize languages for which partial commutation closures give regular languages. Lastly, we show that for input automata with simple idempotents over a binary alphabet and with a constraint language given by a partial automaton with up to three states, the constrained synchronization problem is in P.
Publication Year: 2022
Publication Date: 2022-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot