Experimental Study of the Shortest Reset Word of Random Automata

DOI10.1007/978-3-642-22256-6_27zbMath1297.68167OpenAlexW1790488621MaRDI QIDQ5200075

No author found.

Publication date: 29 July 2011

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

Full work available at URL: https://doi.org/10.1007/978-3-642-22256-6_27

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (10)

Using SAT solvers for synchronization issues in non-deterministic automata ⋮ Careful synchronization of partial deterministic finite automata ⋮ Primitive digraphs with large exponents and slowly synchronizing automata ⋮ Synchronizing random automata on a 4-letter alphabet ⋮ Checking Whether an Automaton Is Monotonic Is NP-complete ⋮ Fast synchronization of inhomogenous random automata ⋮ D2-SYNCHRONIZATION IN NONDETERMINISTIC AUTOMATA ⋮ On the Synchronizing Probability Function and the Triple Rendezvous Time for Synchronizing Automata ⋮ Černý's conjecture and the road colouring problem ⋮ Computing the shortest reset words of synchronizing automata

Uses Software

• MiniSat

Cites Work

• Unnamed Item
• Synchronizing automata with a letter of deficiency 2
• The range order of a product of i transformations from a finite full transformation semigroup
• Approximating the minimum length of synchronizing words is hard
• SAT local search algorithms: Worst-case study
• Clause Shortening Combined with Pruning Yields a New Upper Bound for Deterministic SAT Algorithms
• Reset Sequences for Monotonic Automata
• Slowly Synchronizing Automata and Digraphs
• The Complexity of Finding Reset Words in Finite Automata
• Genetic Algorithm for Synchronization
• On two Combinatorial Problems Arising from Automata Theory
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing

This page was built for publication: Experimental Study of the Shortest Reset Word of Random Automata