zbMATH — the first resource for mathematics

TamMeD: A tableau method for deduction modulo. (English) Zbl 1126.68560
Basin, David (ed.) et al., Automated reasoning. Second international joint conference, IJCAR 2004, Cork, Ireland, July 4–8, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22345-2/pbk). Lecture Notes in Computer Science 3097. Lecture Notes in Artificial Intelligence, 445-459 (2004).
Summary: Deduction modulo is a formalism introduced to separate cleanly computations and deductions by reasoning modulo a congruence on propositions. A sequent calculus modulo has been defined by Dowek, Hardin and Kirchner as well as a resolution-based proof search method called Extended Narrowing And Resolution (ENAR), in which the congruences are handled through rewrite rules on terms and atomic propositions.
We define a tableau-based proof search method, called Tableau Method for Deduction modulo (TaMeD), for theorem proving modulo. We then give a syntactic proof of the completeness of the method with respect to provability in the sequent calculus modulo. Moreover, we follow in our proofs the same steps as the ENAR method in such a way that it allows to try and compare the characteristics of both methods.
For the entire collection see [Zbl 1088.68001].

68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
Full Text: DOI