Certifying DFA bounds for recognition and separation

DOI10.1007/978-3-030-88885-5_4zbMath1497.68273arXiv2107.01566OpenAlexW3210219611MaRDI QIDQ2147179

Nir Lavee, Salomon Sickert, Orna Kupferman

Publication date: 22 June 2022

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

Mathematics Subject Classification ID

Applications of game theory (91A80) Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Learning regular sets from queries and counterexamples
• Recognizing safety and liveness
• Inferring regular languages and \(\omega\)-languages
• Certifying inexpressibility
• Separating Regular Languages with First-Order Logic
• Beyond Hyper-Minimisation--Minimising DBAs and DPAs is NP-Complete
• Linear Automaton Transformations
• Exact DFA Identification Using SAT Solvers
• Complexity of automaton identification from given data
• State Reduction in Incompletely Specified Finite-State Machines
• Computing Minimal Separating DFAs and Regular Invariants Using SAT and SMT Solvers
• O-Minimal Invariants for Discrete-Time Dynamical Systems
• Fixing the State Budget: Approximation of Regular Languages with Small DFAs
• Tools and Algorithms for the Construction and Analysis of Systems
• Efficient Separability of Regular Languages by Subsequences and Suffixes
• Solving Sequential Conditions by Finite-State Strategies
• Model checking of safety properties