Combining Lists with Non-Stably Infinite Theories

Pascal Fontaine 1 Silvio Ranise 2 Calogero Zarba 2
1 MOSEL - Proof-oriented development of computer-based systems
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
2 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In program verification one has often to reason about lists over elements of a given nature. Thus, it becomes important to be able to combine the theory of lists with a generic theory $T$ modeling the elements. This combination can be achieved using the Nelson-Oppen method only if $T$ is stably infinite. The goal of this paper is to relax the stable-infiniteness requirement. More specifically, we provide a new method that is able to combine the theory of lists with any theory $T$ of the elements, regardless of whether $T$ is stably infinite or not. The crux of our combination method is to guess an arrangement over a set of variables that is larger than the one considered by Nelson and Oppen. Furthermore, our results entail that it is also possible to combine $T$ with the more general theory of lists with a length function.
Keywords : combination decision procedure lists arithmetic
Type de document :
Communication dans un congrès
Franz Baader; Andrei Voronkov. 11th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR'04), Mar 2005, Montevideo/Uruguay, Springer-Verlag, 3452, pp.51--66, 2005, Lecture Notes in Computer Science. 〈10.1007/b106931〉
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00000481
Contributeur : Pascal Fontaine <>
Soumis le : vendredi 21 octobre 2005 - 18:00:04
Dernière modification le : vendredi 6 juillet 2018 - 15:06:09
Document(s) archivé(s) le : jeudi 1 avril 2010 - 22:53:09

Fichiers

FontaineRaniseZarba.pdf

Identifiants

Collections

INRIA | UNIV-FCOMTE | UNIV-BM | FEMTO-ST | UNIV-BM-THESE | LORIA | UNIV-LORRAINE

Citation

Pascal Fontaine, Silvio Ranise, Calogero Zarba. Combining Lists with Non-Stably Infinite Theories. Franz Baader; Andrei Voronkov. 11th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR'04), Mar 2005, Montevideo/Uruguay, Springer-Verlag, 3452, pp.51--66, 2005, Lecture Notes in Computer Science. 〈10.1007/b106931〉. 〈inria-00000481〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

338

Téléchargements de fichiers

157

Contact


archive-ouverte@inria.fr