The Complexity of Finding Reset Words in Finite Automata
From MaRDI portal
Publication:3586114
DOI10.1007/978-3-642-15155-2_50zbMath1287.68099OpenAlexW3123516944MaRDI QIDQ3586114
Publication date: 3 September 2010
Published in: Mathematical Foundations of Computer Science 2010 (Search for Journal in Brave)
Full work available at URL: http://publications.rwth-aachen.de/record/119910
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Using SAT solvers for synchronization issues in non-deterministic automata ⋮ Primitive digraphs with large exponents and slowly synchronizing automata ⋮ Approximating the minimum length of synchronizing words is hard ⋮ Strong Inapproximability of the Shortest Reset Word ⋮ Checking Whether an Automaton Is Monotonic Is NP-complete ⋮ Completely distinguishable automata and the set of synchronizing words ⋮ The NP-completeness of the road coloring problem ⋮ Unnamed Item ⋮ Complexity of problems concerning reset words for cyclic and Eulerian automata ⋮ Preimage problems for deterministic finite automata ⋮ A quadratic algorithm for road coloring ⋮ Complexity of Preimage Problems for Deterministic Finite Automata ⋮ Complexity of a problem concerning reset words for Eulerian binary automata ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ Algebraic synchronization criterion and computing reset words ⋮ Complexity of Problems Concerning Reset Words for Cyclic and Eulerian Automata ⋮ Experimental Study of the Shortest Reset Word of Random Automata ⋮ Approximating Minimum Reset Sequences ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata ⋮ Synchronizing Automata over Nested Words ⋮ Černý's conjecture and the road colouring problem ⋮ Attainable Values of Reset Thresholds ⋮ Synchronizing words for real-time deterministic pushdown automata (extended abstract) ⋮ Primitive Sets of Nonnegative Matrices and Synchronizing Automata ⋮ Computing the shortest reset words of synchronizing automata
