Synchronizing automata on quasi-Eulerian digraph

DOI10.1007/978-3-642-31606-7_8MaRDI QIDQ2914697zbMATH OpenOpenAlexFDO

Authors Mikhail V. Berlinkov

Publication date 20 September 2012

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.3402

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Eulerian and Hamiltonian graphs (05C45) Algebraic theory of languages and automata (68Q70)

Abstract: In 1964 v{C}ern'{y} conjectured that each $n$-state synchronizing automaton posesses a reset word of length at most $(n-1{)}^2$. From the other side the best known upper bound on the reset length (minimum length of reset words) is cubic in $n$. Thus the main problem here is to prove quadratic (in $n$) upper bounds. Since 1964, this problem has been solved for few special classes of sa. One of this result is due to Kari cite{Ka03} for automata with Eulerian digraphs. In this paper we introduce a new approach to prove quadratic upper bounds and explain it in terms of Markov chains and Perron-Frobenius theories. Using this approach we obtain a quadratic upper bound for a generalization of Eulerian automata.

Recommendations

• Synchronizing quasi-Eulerian and quasi-one-cluster automata
• Synchronizing Automata Preserving a Chain of Partial Orders
• An extremal series of Eulerian synchronizing automata
• Lower bounds for the length of reset words in Eulerian automata
• Primitive digraphs with large exponents and slowly synchronizing automata

Cites work

• scientific article; zbMATH DE number 1460605 (Why is no real title available?)
• scientific article; zbMATH DE number 3222112 (Why is no real title available?)
• An extremal problem for two families of sets
• Gaps in the exponent set of primitive matrices
• Modifying the upper bound on the length of minimal synchronizing word
• On a conjecture by Carpi and D'Alessandro
• On two Combinatorial Problems Arising from Automata Theory
• Slowly synchronizing automata and digraphs
• Synchronizing Automata and the Černý Conjecture
• Synchronizing finite automata on Eulerian digraphs.
• The averaging trick and the Černý conjecture
• The synchronizing probability function of an automaton
• The Černý conjecture for one-cluster automata with prime length cycle
• Unzerlegbare, nicht negative Matrizen

Cited in

(6)

• Slowly synchronizing automata and digraphs
• Lower bounds for the length of reset words in Eulerian automata
• An extremal series of Eulerian synchronizing automata
• scientific article; zbMATH DE number 1834666 (Why is no real title available?)
• Primitive digraphs with large exponents and slowly synchronizing automata
• Synchronizing quasi-Eulerian and quasi-one-cluster automata

This page was built for publication: Synchronizing automata on quasi-Eulerian digraph

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