Minimising deterministic Büchi automata precisely using SAT solving

DOI10.1007/978-3-642-14186-7_28MaRDI QIDQ4930600zbMATH OpenOpenAlexFDO

Authors Rüdiger Ehlers

Publication date 29 September 2010

Published in Theory and Applications of Satisfiability Testing – SAT 2010 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-14186-7_28

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• SAT-based minimization of deterministic -automata
• Learn with SAT to minimize Büchi automata
• Advanced automata minimization
• Efficient minimization of deterministic weak -automata
• Beyond hyper-minimisation -- minimising DBAs and DPAs is NP-complete

Cited in

(14)

• Efficient minimization of deterministic weak -automata
• Using SAT solvers for synchronization issues in non-deterministic automata
• Deciding monadic second order logic over -words by specialized finite automata
• Advanced automata minimization
• New optimizations and heuristics for determinization of Büchi automata
• Minimization of visibly pushdown automata using partial Max-SAT
• SAT-based minimization of deterministic -automata
• Exact DFA Identification Using SAT Solvers
• Learn with SAT to minimize Büchi automata
• Minimizing Generalized Büchi Automata
• Divide-and-Conquer Determinization of Büchi Automata Based on SCC Decomposition
• Adapting to the behavior of environments with bounded memory
• On the minimisation of deterministic and history-deterministic generalised (co)Büchi automata
• Mediating for reduction (on minimizing alternating Büchi automata)

Describes a project that uses

Uses Software

• PicoSAT

This page was built for publication: Minimising deterministic Büchi automata precisely using SAT solving

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4930600)