A finite state intersection approach to propositional satisfiability

DOI10.1016/j.tcs.2012.04.030zbMath1243.68272OpenAlexW2001123191MaRDI QIDQ442157

Rodrigo Castaño, José M. 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) Logic in artificial intelligence (68T27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Uses Software

• SBSAT
• FORCE
• sharpSAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations
• Algorithms for the maximum satisfiability problem
• Automata-theoretic techniques for modal logics of programs
• A geometric hierarchy beyond context-free languages
• The state complexities of some basic operations on regular languages
• On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
• Weak Second‐Order Arithmetic and Finite Automata
• Extended Resolution Proofs for Conjoining BDDs
• Hard examples for resolution
• Decision Problems of Finite Automata Design and Related Arithmetics
• The emptiness problem for intersections of regular languages
• Variable and Clause Ordering in an FSA Approach to Propositional Satisfiability
• Theory and Applications of Satisfiability Testing
• Implementation and Application of Automata

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