Automating Automated Reasoning: The Case of Two Generic Automated Reasoning Tools

Zohar, Y., Tishkovsky, D., Schmidt, R. A. and Zamansky, A. (2019)

In Lutz, C., Sattler, U., Tinelli, C., Turhan, A.-Y. and Wolter, F. (eds), Description Logic, Theory Combination, and All That: Essays Dedicated to Franz Baader on the Occasion of His 60th Birthday. Lecture Notes in Computer Science, Vol. 11560, Springer, 610-638. Invited paper. BiBTeX, DOI link to Publisher.

The vision of automated support for the investigation of logics, proposed decades ago, has been implemented in many forms, producing numerous tools that analyze various logical properties (e.g., cut-elimination, semantics, and more). However, full ‘automation of automated reasoning’ in the sense of automatic generation of efficient provers has remained a ‘holy grail’ of the field. Creating a generic prover which can efficiently reason in a given logic is challenging, as each logic may be based on a different language, and involve different inference rules, that require different implementation considerations to achieve efficiency, or even tractability. Two recently introduced generic automated provers apply different approaches to tackle this challenge. MetTeL, based on the formalism of tableaux, automatically generates a prover for a given tableau calculus, by implementing generic proof-search procedures with optimizations applicable to many tableau calculi. Gen2sat, based on the formalism of sequent calculi, shifts the burden of search to the realm of off-the-shelf SAT solvers by applying a uniform reduction of derivability in sequent calculi to SAT. This paper examines these two generic provers, focusing in particular on criteria relevant for comparing their performance and usability. To this end, we evaluate the performance of the tools, and describe the results of a preliminary empirical study where user experiences of expert logicians using the two tools are compared.


Renate A. Schmidt
Home | Publications | Tools | FM Group | School | Man Univ

Last modified: 21 Feb 20
Copyright © 2019 Renate A. Schmidt, School of Computer Science, Man Univ, schmidt@cs.man.ac.uk