Synchronization of Automata with One Undefined or Ambiguous Transition
From MaRDI portal
Publication:2914716
DOI10.1007/978-3-642-31606-7_24zbMath1297.68157OpenAlexW32260586MaRDI QIDQ2914716
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
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Constrained synchronization and subset synchronization problems for weakly acyclic automata ⋮ Using SAT solvers for synchronization issues in non-deterministic automata ⋮ Careful synchronization of partial deterministic finite automata ⋮ 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 ⋮ Ideal separation and general theorems for constrained synchronization and their application to small constraint automata ⋮ D2-SYNCHRONIZATION IN NONDETERMINISTIC AUTOMATA ⋮ Lower Bounds for Synchronizing Word Lengths in Partial Automata ⋮ Constrained synchronization and commutativity ⋮ Computational complexity of synchronization under regular commutative constraints ⋮ The relation between preset distinguishing sequences and synchronizing sequences ⋮ Sync-maximal permutation groups equal primitive permutation groups
Cites Work
- A lower bound for the length of the shortest carefully synchronizing words
- Improved upper bounds on synchronizing nondeterministic automata
- Modifying the Upper Bound on the Length of Minimal Synchronizing Word
- Reset Sequences for Monotonic Automata
- Synchronizing Automata and the Černý Conjecture
- Complexity of Problems Concerning Carefully Synchronizing Words for PFA and Directing Words for NFA
- Algebraic Theory of Automata and Languages
- Theory Is Forever
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
