Approximating minimum reset sequences

DOI10.1007/978-3-642-18098-9_17zbMATH Open1297.68131OpenAlexW125636420MaRDI QIDQ3073634FDOQ3073634

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

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

Mathematics Subject Classification ID

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

Cites Work

• Synchronizing Automata and the Černý Conjecture
• Algorithmic construction of sets for k -restrictions
• Synchronizing generalized monotonic automata
• Synchronizing finite automata on Eulerian digraphs.
• Reset Sequences for Monotonic Automata
• On two Combinatorial Problems Arising from Automata Theory
• The complexity of finding reset words in finite automata
• On the Approximation of Shortest Common Supersequences and Longest Common Subsequences
• 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

Cited In (11)

• Reset Sequences for Monotonic Automata
• Strong inapproximability of the shortest reset word
• Title not available (Why is that?)
• Primitive sets of nonnegative matrices and synchronizing automata
• The relation between preset distinguishing sequences and synchronizing sequences
• 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)