Complexity of Problems Concerning Carefully Synchronizing Words for PFA and Directing Words for NFA
From MaRDI portal
Publication:3569754
DOI10.1007/978-3-642-13182-0_27zbMath1285.68089OpenAlexW1854454907MaRDI QIDQ3569754
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
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (6)
P(l)aying for Synchronization ⋮ Synchronization of Automata with One Undefined or Ambiguous Transition ⋮ 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 ⋮ Synchronization problems in automata without non-trivial cycles
This page was built for publication: Complexity of Problems Concerning Carefully Synchronizing Words for PFA and Directing Words for NFA
