Completely reachable automata: a polynomial algorithm and quadratic upper bounds

DOI10.4230/LIPICS.ICALP.2023.59MaRDI QIDQ6638061zbMATH OpenFDO

Authors Robert Ferens, Marek Szykuła

Publication date 14 November 2024

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2023.59

zbMATH Keywords

complete reachabilityDFAextending wordreachabilityreset thresholdreset wordsimple idempotentsynchronizing automatonsynchronizing wordČerný conjecture

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cited in

(5)

• Reset thresholds of transformation monoids
• Don's conjecture for binary completely reachable automata: an approach and its limitations
• Completely reachable almost group automata
• Completely distinguishable automata and the set of synchronizing words
• A quadratic upper bound on the reset thresholds of synchronizing automata containing a transitive permutation group

This page was built for publication: Completely reachable automata: a polynomial algorithm and quadratic upper bounds

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