Slowly Synchronizing Automata and Digraphs

DOI10.1007/978-3-642-15155-2_7zbMath1287.68088arXiv1005.0129OpenAlexW3122681364MaRDI QIDQ3586072

D. S. Ananichev, Vladimir V. Gusev, Mikhail V. Volkov

Publication date: 3 September 2010

Published in: Mathematical Foundations of Computer Science 2010 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Directed graphs (digraphs), tournaments (05C20)

Related Items (23)

Synchronizing Automata on Quasi-Eulerian Digraph ⋮ Synchronizing Automata of Bounded Rank ⋮ Primitive digraphs with large exponents and slowly synchronizing automata ⋮ Synchronizing random automata on a 4-letter alphabet ⋮ Synchronizing Automata with Extremal Properties ⋮ An algorithm for road coloring ⋮ The road problem and homomorphisms of directed graphs ⋮ Unnamed Item ⋮ Slowly synchronizing automata with zero and noncomplete sets ⋮ Extremal minimality conditions on automata ⋮ Circular automata synchronize with high probability ⋮ Completely reachable automata, primitive groups and the state complexity of the set of synchronizing words ⋮ State complexity of the set of synchronizing words for circular automata and automata over binary alphabets ⋮ On incomplete and synchronizing finite sets ⋮ Algebraic synchronization criterion and computing reset words ⋮ Experimental Study of the Shortest Reset Word of Random Automata ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time ⋮ Reset Complexity of Ideal Languages Over a Binary Alphabet ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata ⋮ An Extremal Series of Eulerian Synchronizing Automata ⋮ Modifying the Upper Bound on the Length of Minimal Synchronizing Word ⋮ Experiments with Synchronizing Automata ⋮ Computing the shortest reset words of synchronizing automata

This page was built for publication: Slowly Synchronizing Automata and Digraphs