Synchronization of automata with one undefined or ambiguous transition
From MaRDI portal
Publication:2914716
DOI10.1007/978-3-642-31606-7_24zbMATH Open1297.68157OpenAlexW32260586MaRDI QIDQ2914716FDOQ2914716
Authors: Pavel Martyugin 
Publication date: 20 September 2012
Published in: Implementation and Application of Automata (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-31606-7_24
Recommendations
- PSPACE-completeness of the problem of checking the careful synchronizability of a partial automaton
- Careful synchronization of partial automata with restricted alphabets
- Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
- Recognizing synchronizing automata with finitely many minimal synchronizing words is PSPACE-complete
- Subset synchronization in monotonic automata
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- Synchronizing Automata and the Černý Conjecture
- Reset Sequences for Monotonic Automata
- Title not available (Why is that?)
- Modifying the upper bound on the length of minimal synchronizing word
- Algebraic Theory of Automata and Languages
- Complexity of problems concerning carefully synchronizing words for PFA and directing words for NFA
- Theory Is Forever
- A lower bound for the length of the shortest carefully synchronizing words
- Directable nondeterministic automata
- Title not available (Why is that?)
- Title not available (Why is that?)
- Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata
- Improved upper bounds on synchronizing nondeterministic automata
Cited In (20)
- Constrained synchronization and commutativity
- On synchronizing unambiguous automata
- Constrained synchronization and subset synchronization problems for weakly acyclic automata
- Synchronizing strategies under partial observability
- Synchronizing weighted automata
- Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata
- Lower bounds for synchronizing word lengths in partial automata
- Computational complexity of synchronization under regular commutative constraints
- Sync-maximal permutation groups equal primitive permutation groups
- The relation between preset distinguishing sequences and synchronizing sequences
- Synchronizing deterministic push-down automata can be really hard
- \(D_2\)-synchronization in nondeterministic automata
- Synchronizing words under \textsf{LTL} constraints
- Careful synchronization of partial deterministic finite automata
- Complexity of problems concerning carefully synchronizing words for PFA and directing words for NFA
- Careful synchronization of partial automata with restricted alphabets
- Using SAT solvers for synchronization issues in non-deterministic automata
- PSPACE-completeness of the problem of checking the careful synchronizability of a partial automaton
- Ideal separation and general theorems for constrained synchronization and their application to small constraint automata
- Synchronization of Parikh automata
This page was built for publication: Synchronization of automata with one undefined or ambiguous transition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2914716)
