Diagrammatic Confluence and Completion - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2009

Diagrammatic Confluence and Completion

Résumé

We give a new elegant proof that decreasing diagrams imply confluence based on a proof reduction technique, which is then the basis of a novel completion method which proof-reduction relation transforms arbitrary proofs into rewrite proofs even in presence of non-terminating reductions. Unlike previous methods, no ordering of the set of terms is required, but can be used if available. Unlike ordered completion, rewrite proofs are closed under instantiation. Examples are presented, including Kleene's and Huet's classical examples showing that non-terminating local-confluent relations may not be confluent.

Dates et versions

inria-00436070 , version 1 (26-11-2009)

Identifiants

Citer

Jean-Pierre Jouannaud, Vincent van Oostrom. Diagrammatic Confluence and Completion. International Conference in Automata, Languages and Programming, Paul Spirakis, Jul 2009, Rhodes, Greece. ⟨10.1007/978-3-642-02930-1_18⟩. ⟨inria-00436070⟩
114 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More