Boolean Quantification in a First-Order Context

作者: Thomas Sturm , Andreas Seidl

DOI:

关键词:

摘要: We establish a framework to integrate propositional logic with first-order logic. This is done in such way that it optionally appears either as over Boolean algebra or including quantification. describe and prove complexity bounds for extended quantifier elimination by virtual substitution our theory. is, besides many other mathematical algorithms utilities, implemented new context ibalp of the reduce package redlog. demonstrate capabilities this means numerous application benchmark examples qsat problems.

参考文章(10)
Jussi Rintanen, Improvements to the evaluation of quantified boolean formulae international joint conference on artificial intelligence. pp. 1192- 1197 ,(1999)
Enrico Giunchiglia, Massimo Narizzano, Armando Tacchella, QUBE: A System for Deciding Quantified Boolean Formulas Satisfiability international joint conference on automated reasoning. pp. 364- 369 ,(2001) , 10.1007/3-540-45744-5_27
Andreas Dolzmann, Thomas Sturm, REDLOG: computer algebra meets computer logic ACM Sigsam Bulletin. ,vol. 31, pp. 2- 9 ,(1997) , 10.1145/261320.261324
D. B. Armstrong, On Finding a Nearly Minimal Set of Fault Detection Tests for Combinational Logic Nets IEEE Transactions on Electronic Computers. ,vol. EC-15, pp. 66- 73 ,(1966) , 10.1109/PGEC.1966.264376
ANDREAS DOLZMANN, THOMAS STURM, Simplification of Quantifier-free Formulae over Ordered Fields Journal of Symbolic Computation. ,vol. 24, pp. 209- 232 ,(1997) , 10.1006/JSCO.1997.0123
VOLKER WEISPFENNING, Simulation and Optimization by Quantifier Elimination Journal of Symbolic Computation. ,vol. 24, pp. 189- 208 ,(1997) , 10.1006/JSCO.1997.0122
Volker Weispfenning, The complexity of linear problems in fields Journal of Symbolic Computation. ,vol. 5, pp. 3- 27 ,(1988) , 10.1016/S0747-7171(88)80003-8
Matthew W. Moskewicz, Conor F. Madigan, Ying Zhao, Lintao Zhang, Sharad Malik, Chaff Proceedings of the 38th conference on Design automation - DAC '01. pp. 530- 535 ,(2001) , 10.1145/378239.379017
Abraham Kandel, Gideon Langholz, Joe L. Mott, Digital Logic Design ,(1988)