Abstract: We present several infinite series of synchronizing automata for which the minimum length of reset words is close to the square of the number of states. These automata are closely related to primitive digraphs with large exponent.
Recommendations
Cited in
(29)- An algorithm for road coloring
- Slowly synchronizing automata with fixed alphabet size
- 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
- Computing the shortest reset words of synchronizing automata
- Slowly synchronizing automata with zero and noncomplete sets
- On the synchronizing probability function and the triple rendezvous time. New approaches to Černý's conjecture
- On the synchronizing probability function and the triple rendezvous time for synchronizing automata
- An extremal series of Eulerian synchronizing automata
- Experiments with Synchronizing Automata
- Synchronizing automata on quasi-Eulerian digraph
- Synchronizing automata of bounded rank
- Synchronizing Automata with Extremal Properties
- Modifying the upper bound on the length of minimal synchronizing word
- Synchronizing Automata with a Letter of Deficiency 2
- Primitive digraphs with large exponents and slowly synchronizing automata
- Synchronizing random automata on a 4-letter alphabet
- Extremal minimality conditions on automata
- scientific article; zbMATH DE number 1834666 (Why is no real title available?)
- Finding short synchronizing words for prefix codes
- On incomplete and synchronizing finite sets
- Experimental study of the shortest reset word of random automata
- Reset complexity of ideal languages over a binary alphabet
- On random primitive sets, directable NFAs and the generation of slowly synchronizing DFAs
- scientific article; zbMATH DE number 7152087 (Why is no real title available?)
- The road problem and homomorphisms of directed graphs
- Synchronizing automata with a letter of deficiency 2
- A series of slowly synchronizing automata with a zero state over a small alphabet
This page was built for publication: Slowly synchronizing automata and digraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3586072)
