Approximating minimum reset sequences

DOI10.1007/978-3-642-18098-9_17MaRDI QIDQ3073634zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Strong inapproximability of the shortest reset word
• Computing the shortest reset words of synchronizing automata
• Approximation of reset thresholds with greedy algorithms
• Synchronizing finite automata with short reset words
• A fast algorithm finding the shortest reset words

Cites work

• Algorithmic construction of sets for k -restrictions
• Generation of constants and synchronization of finite automata
• In extremal combinatorial problem associated with the bound on the length of a synchronizing word in an automaton
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• On two Combinatorial Problems Arising from Automata Theory
• Reset Sequences for Monotonic Automata
• Synchronizing Automata and the Černý Conjecture
• Synchronizing finite automata on Eulerian digraphs.
• Synchronizing generalized monotonic automata
• The complexity of finding reset words in finite automata

Cited in

(11)

• Reset Sequences for Monotonic Automata
• Strong inapproximability of the shortest reset word
• scientific article; zbMATH DE number 4082982 (Why is no real title available?)
• The relation between preset distinguishing sequences and synchronizing sequences
• Primitive sets of nonnegative matrices and synchronizing automata
• Checking whether an automaton is monotonic is NP-complete
• Černý's conjecture and the road colouring problem
• A multi-parameter analysis of hard problems on deterministic finite automata
• Finding short synchronizing words for prefix codes
• Computing the shortest reset words of synchronizing automata
• Approximation of reset thresholds with greedy algorithms

This page was built for publication: Approximating minimum reset sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3073634)