Experiments with Synchronizing Automata
From MaRDI portal
Abstract: We have improved an algorithm generating synchronizing automata with a large length of the shortest reset words. This has been done by refining some known results concerning bounds on the reset length. Our improvements make possible to consider a number of conjectures and open questions concerning synchronizing automata, checking them for automata with a small number of states and discussing the results. In particular, we have verified the v{C}ern'y conjecture for all binary automata with at most 12 states, and all ternary automata with at most 8 states.
Recommendations
- Experiments on Synchronizing Automata
- scientific article; zbMATH DE number 826076
- Optimal synchronizing experiments with linear automata
- Synchronised automata
- Synchronization of finite automata
- Synchronizing automata with coinciding cycles
- Synchronizing random automata
- Synchronization of Regular Automata
- Synchronizing Automata with Extremal Properties
- Synchronizing non-deterministic finite automata
Cites work
- A counter example to a conjecture concerning synchronizing words in finite automata
- A note on a recent attempt to improve the Pin-Frankl bound
- A quadratic upper bound on the size of a synchronizing word in one-cluster automata
- An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Černy Conjecture
- An extremal problem for two families of sets
- Developments in Language Theory
- Generating small automata and the Černý conjecture
- Independent sets of words and the synchronization problem
- Matrix Mortality and the Černý-Pin Conjecture
- Modifying the upper bound on the length of minimal synchronizing word
- On two Combinatorial Problems Arising from Automata Theory
- Primitive digraphs with large exponents and slowly synchronizing automata
- Reset Sequences for Monotonic Automata
- Slowly synchronizing automata and digraphs
- Synchronizing Automata and the Černý Conjecture
- The averaging trick and the Černý conjecture
- The Černý conjecture for one-cluster automata with prime length cycle
Cited in
(19)- Synchronizing automata with a letter of deficiency 2
- An improved algorithm for finding the shortest synchronizing words
- Experimental study of the shortest reset word of random automata
- Counting symbol switching in synchronizing automata
- Lower bounds for synchronizing word lengths in partial automata
- Attainable values of reset thresholds
- Optimal synchronizing experiments with linear automata
- Slowly synchronizing automata with fixed alphabet size
- Synchronizing Automata with a Letter of Deficiency 2
- Generating small automata and the Černý conjecture
- Extremal synchronizing circular automata
- Černý's conjecture and the road colouring problem
- Computing the shortest reset words of synchronizing automata
- Experiments on Synchronizing Automata
- An extremal series of Eulerian synchronizing automata
- scientific article; zbMATH DE number 7228447 (Why is no real title available?)
- Implementation of the algorithm for testing an automaton for synchronization in linear expected time
- Synchronizing sequences for road colored digraphs
- A linear bound on the \(k\)-rendezvous time for primitive sets of NZ matrices
This page was built for publication: Experiments with Synchronizing Automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830218)
