Synchronization of automata with one undefined or ambiguous transition
From MaRDI portal
Publication:2914716
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
Cites work
- scientific article; zbMATH DE number 3545583 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 2016847 (Why is no real title available?)
- scientific article; zbMATH DE number 3222112 (Why is no real title available?)
- A lower bound for the length of the shortest carefully synchronizing words
- Algebraic Theory of Automata and Languages
- Complexity of problems concerning carefully synchronizing words for PFA and directing words for NFA
- Directable nondeterministic automata
- Improved upper bounds on synchronizing nondeterministic automata
- Lower bounds for the length of the shortest carefully synchronizing words for two- and three-letter partial automata
- Modifying the upper bound on the length of minimal synchronizing word
- Reset Sequences for Monotonic Automata
- Synchronizing Automata and the Černý Conjecture
- Theory Is Forever
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
- Careful synchronization of partial deterministic finite automata
- Synchronizing words under \textsf{LTL} constraints
- 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)
