A finite state intersection approach to propositional satisfiability

DOI10.1016/J.TCS.2012.04.030MaRDI QIDQ442157zbMATH OpenOpenAlexFDO

Authors José M. Castaño, Rodrigo Castaño

Publication date 9 August 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.04.030

zbMATH Keywords

model countingALL-SATFSA intersectionintersection grammars (FSIG)regular expression compilation

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Logic in artificial intelligence (68T27)

Recommendations

• Variable and clause ordering in an FSA approach to propositional satisfiability
• Theory and Applications of Satisfiability Testing
• scientific article; zbMATH DE number 2084702
• Symbolic techniques in satisfiability solving
• Exact DFA Identification Using SAT Solvers

Cites work

• scientific article; zbMATH DE number 5277949 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1222108 (Why is no real title available?)
• scientific article; zbMATH DE number 2038699 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• A geometric hierarchy beyond context-free languages
• Algorithms for the maximum satisfiability problem
• Automata-theoretic techniques for modal logics of programs
• Counter-free automata, first-order logic, and star-free expressions extended by prefix oracles
• Decision Problems of Finite Automata Design and Related Arithmetics
• Extended Resolution Proofs for Conjoining BDDs
• Hard examples for resolution
• Implementation and Application of Automata
• On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
• Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations
• The emptiness problem for intersections of regular languages
• The state complexities of some basic operations on regular languages
• Theory and Applications of Satisfiability Testing
• Variable and clause ordering in an FSA approach to propositional satisfiability
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(2)

• scientific article; zbMATH DE number 5205481 (Why is no real title available?)
• Variable and clause ordering in an FSA approach to propositional satisfiability

Describes a project that uses

Uses Software

• sharpSAT
• FORCE
• SBSAT

This page was built for publication: A finite state intersection approach to propositional satisfiability

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