PSPACE-completeness of the problem of checking the careful synchronizability of a partial automaton

MaRDI QIDQ3450095zbMATH OpenFDO

Authors Pavel Martyugin

Publication date 2 November 2015

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Recommendations

• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• Synchronization of automata with one undefined or ambiguous transition
• Complexity of problems concerning carefully synchronizing words for PFA and directing words for NFA
• Recognizing synchronizing automata with finitely many minimal synchronizing words is PSPACE-complete
• Complexity of checking whether two automata are synchronized by the same language

Cited in

(4)

• Synchronization of automata with one undefined or ambiguous transition
• Recognizing synchronizing automata with finitely many minimal synchronizing words is PSPACE-complete
• Complexity of problems concerning carefully synchronizing words for PFA and directing words for NFA
• Complexity of checking whether two automata are synchronized by the same language

This page was built for publication: PSPACE-completeness of the problem of checking the careful synchronizability of a partial automaton

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3450095)