Complexity of problems concerning carefully synchronizing words for PFA and directing words for NFA

DOI10.1007/978-3-642-13182-0_27MaRDI QIDQ3569754zbMATHOpenAlexFDO

Authors Pavel Martyugin

Publication date 22 June 2010

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-13182-0_27

zbMATH Keywords

computational complexitysynchronizationautomatadirecting words

Mathematics Subject Classification ID

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

Recommendations

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

Cited in

(6)

• On the computational complexity of problems related to distinguishability sets
• Synchronization of automata with one undefined or ambiguous transition
• The relation between preset distinguishing sequences and synchronizing sequences
• Complexity of checking whether two automata are synchronized by the same language
• Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
• PSPACE-completeness of the problem of checking the careful synchronizability of a partial automaton

This page was built for publication: Complexity of problems concerning carefully synchronizing words for PFA and directing words for NFA

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