Approximating Minimum Reset Sequences

DOI10.1007/978-3-642-18098-9_17zbMath1297.68131MaRDI 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

68Q45: Formal languages and automata

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68W25: Approximation algorithms

Related Items

Unnamed Item, The relation between preset distinguishing sequences and synchronizing sequences, Approximating the minimum length of synchronizing words is hard, Černý's conjecture and the road colouring problem, A multi-parameter analysis of hard problems on deterministic finite automata, Algebraic synchronization criterion and computing reset words, Computing the shortest reset words of synchronizing automata, Strong Inapproximability of the Shortest Reset Word, Checking Whether an Automaton Is Monotonic Is NP-complete, Primitive Sets of Nonnegative Matrices and Synchronizing Automata

Cites Work

• Unnamed Item
• 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