Synchronization of Automata with One Undefined or Ambiguous Transition

DOI10.1007/978-3-642-31606-7_24zbMath1297.68157OpenAlexW32260586MaRDI QIDQ2914716

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

zbMATH Keywords

computational complexitynondeterministic automatasynchronizing wordscareful synchronization

Mathematics Subject Classification ID

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