From Diagrammatic Confluence to Modularity - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 2012

From Diagrammatic Confluence to Modularity

Résumé

This paper builds on a fundamental notion of rewriting theory that characterizes confluence of a (binary) rewriting relation, Klop's cofinal derivations. Cofinal derivations were used by van Oostrom to obtain another characterization of confluence of a rewriting relation via the existence of decreasing diagrams for all local peaks. In this paper, we show that cofinal derivations can be used to give a new, concise proof of Toyama's celebrated modularity theorem and its recent extensions to rewriting modulo in the case of strongly-coherent systems, an assumption discussed in depth here. This is done by generalizing cofinal derivations to cofinal streams, allowing us in turn to generalize van Oostrom's result to the modulo case.

Dates et versions

hal-00730272 , version 1 (08-09-2012)

Identifiants

Citer

Jean-Pierre Jouannaud, Jiaxiang Liu. From Diagrammatic Confluence to Modularity. Theoretical Computer Science, 2012, 9032, ⟨10.1016/j.tcs.2012.08.030⟩. ⟨hal-00730272⟩
164 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More