Synchronizing automata on quasi-Eulerian digraph

DOI10.1007/978-3-642-31606-7_8zbMATH Open1297.68107arXiv1203.3402OpenAlexW1934547033MaRDI QIDQ2914697FDOQ2914697

Authors: Mikhail V. Berlinkov 

Publication date: 20 September 2012

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• Slowly synchronizing automata and digraphs
• Title not available (Why is that?)

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)