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.68089MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Synchronization problems in automata without non-trivial cycles, The relation between preset distinguishing sequences and synchronizing sequences, 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, P(l)aying for Synchronization, Synchronization of Automata with One Undefined or Ambiguous Transition