Book chapter
A new correctness proof of the Nelson-Oppen combination procedure
Frontiers of Combining Systems, Vol.3, pp.103-119
Applied Logic Series, 3, KLUWER ACADEMIC PUBL
1996
Abstract
The Nelson-Oppen combination procedure, which combines satisfiability procedures for a class of first-order theories by propagation of equalities between variables, is one of the most general combination methods in the field of theory combination. We describe a new nondeterministic version of the procedure that has been used to extend the Constraint Logic Programming Scheme to unions of constraint theories. The correctness proof of the procedure that we give in this paper not only constitutes a novel and easier proof of Nelson and Oppen's original results, but also shows that equality sharing between the satisfiability procedures of the component theories, the main idea of the method, can be confined to a restricted set of variables.
While working on the new correctness proof, we also found a new characterization of the consistency of the union of first-order theories. We discuss and give a proof of such characterization as well.
Details
- Title: Subtitle
- A new correctness proof of the Nelson-Oppen combination procedure
- Creators
- Cesare TinelliMehdi Harandi
- Contributors
- F Baader (Editor)K U Schulz (Editor)
- Resource Type
- Book chapter
- Publication Details
- Frontiers of Combining Systems, Vol.3, pp.103-119
- Publisher
- KLUWER ACADEMIC PUBL
- Series
- Applied Logic Series; 3
- Number of pages
- 17
- Language
- English
- Date published
- 1996
- Academic Unit
- Computer Science
- Record Identifier
- 9984411252202771
Metrics
2 Record Views