Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata

DOI10.1007/s00224-013-9516-6zbMath1380.68257OpenAlexW2140195055MaRDI QIDQ1678755

Pavel Martyugin

Publication date: 7 November 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-013-9516-6

zbMATH Keywords

computational complexityautomatasynchronizationdirecting words

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (20)

Primitivity and Hurwitz Primitivity of Nonnegative Matrix Tuples: A Unified Approach ⋮ On automata recognizing birecurrent sets ⋮ Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ Some results concerning careful synchronization of partial automata and subset synchronization of DFA's ⋮ Unnamed Item ⋮ Careful synchronization of partial deterministic finite automata ⋮ Synchronization of Parikh automata ⋮ Distributed graph problems through an automata-theoretic lens ⋮ Synchronizing deterministic push-down automata can be really hard ⋮ Preimage problems for deterministic finite automata ⋮ Complexity of Preimage Problems for Deterministic Finite Automata ⋮ The complexity of synchronizing Markov decision processes ⋮ Unnamed Item ⋮ Reset Complexity of Ideal Languages Over a Binary Alphabet ⋮ Unnamed Item ⋮ Synchronizing Automata over Nested Words ⋮ Semicomputable points in Euclidean spaces ⋮ Primitive Sets of Nonnegative Matrices and Synchronizing Automata ⋮ Synchronizing series-parallel deterministic finite automata with loops and related problems ⋮ Distributed graph problems through an automata-theoretic Lens

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound for the length of the shortest carefully synchronizing words
• Improved upper bounds on synchronizing nondeterministic automata
• Relationships between nondeterministic and deterministic tape complexities
• Synchronization of Automata with One Undefined or Ambiguous Transition
• 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

This page was built for publication: Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata