Approximating Minimum Reset Sequences

DOI10.1007/978-3-642-18098-9_17zbMath1297.68131OpenAlexW125636420MaRDI QIDQ3073634

Michael Gerbush, Brent Heeringa

Publication date: 11 February 2011

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-18098-9_17

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (10)

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 ⋮ Unnamed Item ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ Algebraic synchronization criterion and computing reset words ⋮ The relation between preset distinguishing sequences and synchronizing sequences ⋮ Černý's conjecture and the road colouring problem ⋮ Primitive Sets of Nonnegative Matrices and Synchronizing Automata ⋮ Computing the shortest reset words of synchronizing automata

Cites Work

• Synchronizing finite automata on Eulerian digraphs.
• Approximating the minimum length of synchronizing words is hard
• Synchronizing generalized monotonic automata
• Algorithmic construction of sets for k -restrictions
• In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• The Complexity of Finding Reset Words in Finite Automata
• On two Combinatorial Problems Arising from Automata Theory
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• Unnamed Item

This page was built for publication: Approximating Minimum Reset Sequences