Synchronizing quasi-Eulerian and quasi-one-cluster automata

DOI10.1142/S0129054113400157MaRDI QIDQ5401552zbMATH OpenOpenAlexFDO

Authors Mikhail V. Berlinkov

Publication date 10 March 2014

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054113400157

zbMATH Keywords

Černý conjectureextension methodMarkov chainsprimitive matricessynchronizing automata

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Formal languages and automata (68Q45)

Recommendations

• Synchronizing automata on quasi-Eulerian digraph
• An extremal series of Eulerian synchronizing automata
• Synchronizing Automata with Extremal Properties
• Lower bounds for the length of reset words in Eulerian automata
• scientific article; zbMATH DE number 846959

Cites work

• A quadratic upper bound on the size of a synchronizing word in one-cluster automata
• An extremal problem for two families of sets
• On a conjecture by Carpi and D'Alessandro
• Synchronizing finite automata on Eulerian digraphs.
• The averaging trick and the Černý conjecture
• The Černý conjecture for one-cluster automata with prime length cycle
• The synchronizing probability function of an automaton
• Unzerlegbare, nicht negative Matrizen

Cited in

(7)

• Preimage problems for deterministic finite automata
• An extremal series of Eulerian synchronizing automata
• Lower bounds for the length of reset words in Eulerian automata
• Synchronizing automata on quasi-Eulerian digraph
• Synchronizing Automata with Extremal Properties
• scientific article; zbMATH DE number 7228447 (Why is no real title available?)
• Complexity of preimage problems for deterministic finite automata

This page was built for publication: Synchronizing quasi-Eulerian and quasi-one-cluster automata

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