Publication details

Saarland University Computer Science

Analytic Tableaux for Higher-Order Logic with Choice

Julian Backes, Chad E. Brown

Automated Reasoning: 5th International Joint Conference, IJCAR 2010, Edinburgh, UK, July 16-19, 2010, Proceedings, Vol. 6173 of LNCS/LNAI, pp. 76--90, Springer, 2010

While many higher-order interactive theorem provers include a choice operator, higher-order automated theorem provers currently do not. As a step towards supporting automated reasoning in the presence of a choice operator, we present a cut-free ground tableau calculus for Church’s simple type theory with choice. The tableau calculus is designed with automated search in mind. In particular, the rules only operate on the top level structure of formulas. Additionally, we restrict the instantiation terms for quantifiers to a universe that depends on the current branch. At base types the universe of instantiations is finite. We prove completeness of the tableau calculus relative to Henkin models.

Download PDF        Show BibTeX        Download slides (PDF)       

Login to edit

Webmaster, Wed Sep 16 10:47:00 2009