2010 | OriginalPaper | Chapter
RegSTAB: A SAT Solver for Propositional Schemata
Authors : Vincent Aravantinos, Ricardo Caferra, Nicolas Peltier
Published in: Automated Reasoning
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We describe the system Reg
Stab
(for
reg
ular
s
chemata
tab
leau) that solves the satisfiability problem for a class of propositional schemata. Our formalism extends propositional logic by considering
indexed propositions
(such as
$P_1,P_{{\tt i}},P_{{\tt j}+1},\ldots$
) and
iterated connectives
(e.g.
$\bigvee_{i={\tt i}}^{\tt n} \phi$
). The indices and bounds are linear arithmetic expressions (possibly containing variables, interpreted as integers). Our system allows one to check the satisfiability of sequences of formulae such as
$(\bigvee_{{\tt i}=1}^{\tt n} P_{\tt i}) \wedge (\bigwedge_{{\tt i}=1}^{\tt n} \neg P_{\tt i})$
.