Complexity of problems concerning carefully synchronizing words for PFA and directing words for NFA
DOI10.1007/978-3-642-13182-0_27zbMATH Open1285.68089OpenAlexW1854454907MaRDI QIDQ3569754FDOQ3569754
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
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
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (6)
- Synchronization problems in automata without non-trivial cycles
- Approximating the minimum length of synchronizing words is hard
- Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
- The relation between preset distinguishing sequences and synchronizing sequences
- P(l)aying for synchronization
- Synchronization of automata with one undefined or ambiguous transition
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)
