Combining Lists with Non-Stably Infinite Theories - Inria - Institut national de recherche en sciences et technologies du numérique Access content directly
Conference Papers Year : 2005

Combining Lists with Non-Stably Infinite Theories

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.
Fichier principal
Vignette du fichier
FontaineRaniseZarba.pdf (210.53 Ko) Télécharger le fichier
Loading...

Dates and versions

inria-00000481 , version 1 (21-10-2005)

Identifiers

Cite

Pascal Fontaine, Silvio Ranise, Calogero G. Zarba. Combining Lists with Non-Stably Infinite Theories. 11th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR'04), Mar 2005, Montevideo/Uruguay, pp.51--66, ⟨10.1007/b106931⟩. ⟨inria-00000481⟩
160 View
348 Download

Altmetric

Share

Gmail Facebook X LinkedIn More