Using SAT solvers for synchronization issues in non-deterministic automata

DOI10.17377/semi.2018.15.117zbMath1411.68053arXiv1801.05391OpenAlexW2997019898MaRDI QIDQ2633380

Hanan Shabana, Mikhail V. Volkov

Publication date: 8 May 2019

Published in: Sibirskie Èlektronnye Matematicheskie Izvestiya (Search for Journal in Brave)

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

zbMATH Keywords

SATsynchronizing wordnondeterministic automatonSAT-solverrandom automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Careful synchronization of partial deterministic finite automata ⋮ D2-SYNCHRONIZATION IN NONDETERMINISTIC AUTOMATA

Uses Software

• MiniSat
• CryptoMiniSat
• Lingeling

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A lower bound for the length of the shortest carefully synchronizing words
• On primitivity of sets of matrices
• Polynomial complete problems in automata theory
• Computing the shortest reset words of synchronizing automata
• DFAs and PFAs with long shortest synchronizing word length
• Synchronization of Automata with One Undefined or Ambiguous Transition
• Primitive Sets of Nonnegative Matrices and Synchronizing Automata
• Synchronizing Automata and the Černý Conjecture
• The Complexity of Finding Reset Words in Finite Automata
• On two Combinatorial Problems Arising from Automata Theory
• Asymptotic estimate of the length of a diagnostic word for a finite automaton
• Synchronizing non-deterministic finite automata
• Algebraic Theory of Automata and Languages
• Experimental Study of the Shortest Reset Word of Random Automata
• Theory and Applications of Satisfiability Testing
• Lower Bounds for Synchronizing Word Lengths in Partial Automata
• Experimental Evaluation of Classical Automata Constructions

This page was built for publication: Using SAT solvers for synchronization issues in non-deterministic automata