inria-00591414, version 4
Expressing Polymorphic Types in a Many-Sorted Language
François Bobot
1, 2Andrei Paskevich
1, 2
(2011)
Abstract: In this paper, we study translation from a first-order logic with polymorphic types à la ML (of which we give a formal description) to a many-sorted or one-sorted logic as accepted by mainstream automated theorem provers. We consider a three-stage scheme where the last stage eliminates polymorphic types while adding the necessary "annotations" to preserve soundness, and the first two stages serve to protect certain terms so that they can keep their original unannotated form. This protection allows us to make use of provers' built-in theories and operations. We present two existing translation procedures as sound and complete instances of this generic scheme. Our formulation generalizes over the previous ones by allowing us to protect terms of arbitrary monomorphic types. In particular, we can benefit from the built-in theory of arrays in SMT solvers such as Z3, CVC3, and Yices. The proposed methods are implemented in the Why3 tool and we compare their performance in combination with several automated provers.
- 1: PROVAL (INRIA Saclay - Ile de France)
- INRIA – Université Paris XI - Paris Sud – CNRS : UMR
- 2: Laboratoire de Recherche en Informatique (LRI)
- CNRS : UMR8623 – Université Paris XI - Paris Sud
- Domain : Computer Science/Logic in Computer Science
- Keywords : automated theorem proving – polymorphic types – many-sorted first-order logic – satisfiability modulo theory
- Available versions : v1 (2011-05-09) v2 (2011-05-09) v3 (2011-07-11) v4 (2011-07-26)
- inria-00591414, version 4
- http://hal.inria.fr/inria-00591414
- oai:hal.inria.fr:inria-00591414
- From: Andrei Paskevich
- Submitted on: Tuesday, 26 July 2011 12:12:15
- Updated on: Tuesday, 26 July 2011 21:06:51






Associated documents
Export