Skip to Main content Skip to Navigation
Conference papers

A proof of weak termination providing the right way to terminate

Olivier Fissore 1 Isabelle Gnaedig 1 Hélène Kirchner 1
1 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We give an inductive method for proving weak innermost termination of rule-based programs, from which we automatically infer, for each successful proof, a finite strategy for data evaluation. We first present the proof principle, using an explicit induction on the termination property, to prove that any input data has at least one finite evaluation. For that, we observe proof trees built from the rewrite system, schematizing the innermost derivations of any ground term. These proof trees are issued from patterns representing sets of ground terms. They are built using two mechanisms, namely abstraction, introducing variables that represent ground terms in normal form, and narrowing, schematizing rewriting on ground terms. Then, we show how, for any ground term, a rewriting strategy to compute one of its normal forms can be extracted from the proof trees, even if the ground term admits infinite rewriting derivations.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/inria-00100120
Contributor : Publications Loria <>
Submitted on : Wednesday, October 10, 2018 - 8:34:30 PM
Last modification on : Friday, February 26, 2021 - 3:28:06 PM

File

70-preprint.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Olivier Fissore, Isabelle Gnaedig, Hélène Kirchner. A proof of weak termination providing the right way to terminate. First International Colloquium on Theoretical Aspects of Computing, 2004, Guiyang, Chine, France. 15 p, ⟨10.1007/978-3-540-31862-0⟩. ⟨inria-00100120⟩

Share

Metrics

Record views

361

Files downloads

234