Approximation of reset thresholds with greedy algorithms

DOI10.3233/FI-2016-1357MaRDI QIDQ4976394zbMATH OpenOpenAlexFDO

Authors D. S. Ananichev, Vladimir V. Gusev

Publication date 28 July 2017

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2016-1357

zbMATH Keywords

approximation algorithmgreedy algorithminapproximabilityreset thresholdsynchronizing automatasynchronizing word

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Approximation algorithms (68W25)

Recommendations

• Approximating minimum reset sequences
• Strong inapproximability of the shortest reset word
• Synchronizing finite automata with short reset words
• Computing the shortest reset words of synchronizing automata
• On two algorithmic problems about synchronizing automata (short paper)

Cited in

(7)

• Černý's conjecture and the road colouring problem
• Preimage problems for deterministic finite automata
• Approximating minimum reset sequences
• scientific article; zbMATH DE number 7228447 (Why is no real title available?)
• Complexity of preimage problems for deterministic finite automata
• Attainable values of reset thresholds
• A linear bound on the \(k\)-rendezvous time for primitive sets of NZ matrices

This page was built for publication: Approximation of reset thresholds with greedy algorithms

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