| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [23 references]
https://hal.inria.fr/inria-00000481
Contributor : Pascal Fontaine <>
Submitted on : Friday, October 21, 2005 - 6:00:04 PM
Last modification on : Friday, July 6, 2018 - 3:06:09 PM
Document(s) archivé(s) le : Thursday, April 1, 2010 - 10:53:09 PM
Contributor : Pascal Fontaine <>
Submitted on : Friday, October 21, 2005 - 6:00:04 PM
Last modification on : Friday, July 6, 2018 - 3:06:09 PM
Document(s) archivé(s) le : Thursday, April 1, 2010 - 10:53:09 PM