Projections for Infinitary Rewriting

Carlos Lombardi, Alejandro Ríos, Roel de Vrijer

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

Proof terms in term rewriting are a representation means for reduction sequences, and more in general for contraction activity, allowing to distinguish e.g. simultaneous from sequential reduction. Proof terms for finitary, first-order, left-linear term rewriting are described in [Terese. Term Rewriting Systems, volume 55 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, UK, 2003], ch. 8. In a previous work [C. Lombardi, A. Ríos, and R. de Vrijer. Proof terms for infinitary rewriting. In G. Dowek, editor, RTA-TLCA'14, volume 8560 of Lecture Notes in Computer Science, pages 303–318. Springer, 2014] we defined an extension of the finitary proof-term formalism, that allows to describe contractions in infinitary first-order term rewriting, and gave a characterisation of permutation equivalence. In this work, we discuss how projections of possibly infinite rewrite sequences can be modeled using proof terms. Again, the foundation is a characterisation of projections for finitary rewriting described in [Terese. Term Rewriting Systems, volume 55 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, UK, 2003], Sec. 8.7. We extend this characterisation to infinitary rewriting and also refine it, by describing precisely the role that structural equivalence plays in the development of the notion of projection. The characterisation we propose yields a definite expression, i.e. a proof term, that describes the projection of an infinitary reduction over another. To illustrate the working of projections, we show how a common reduct of a (possibly infinite) reduction and a single step that makes part of it can be obtained via their respective projections. We show, by means of several examples, that the proposed definition yields the expected behavior also in cases beyond those covered by this result. Finally, we discuss how the notion of limit is used in our definition of projection for infinite reduction.

Original languageEnglish
Pages (from-to)131-148
Number of pages18
JournalElectronic Notes in Theoretical Computer Science
Volume332
DOIs
Publication statusPublished - 11 Jun 2017

Fingerprint

Rewriting
Projection
Computer science
Term Rewriting
Term
Term Rewriting Systems
Computer Science
Contraction
Rapid thermal annealing
Equivalence
First-order
Reduct
Permutation

Keywords

  • infinitary term rewriting
  • permutation equivalence
  • projection
  • proof terms

Cite this

Lombardi, Carlos ; Ríos, Alejandro ; de Vrijer, Roel. / Projections for Infinitary Rewriting. In: Electronic Notes in Theoretical Computer Science. 2017 ; Vol. 332. pp. 131-148.
@article{a7caecb6542f416e9a72c0c00e1eae21,
title = "Projections for Infinitary Rewriting",
abstract = "Proof terms in term rewriting are a representation means for reduction sequences, and more in general for contraction activity, allowing to distinguish e.g. simultaneous from sequential reduction. Proof terms for finitary, first-order, left-linear term rewriting are described in [Terese. Term Rewriting Systems, volume 55 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, UK, 2003], ch. 8. In a previous work [C. Lombardi, A. R{\'i}os, and R. de Vrijer. Proof terms for infinitary rewriting. In G. Dowek, editor, RTA-TLCA'14, volume 8560 of Lecture Notes in Computer Science, pages 303–318. Springer, 2014] we defined an extension of the finitary proof-term formalism, that allows to describe contractions in infinitary first-order term rewriting, and gave a characterisation of permutation equivalence. In this work, we discuss how projections of possibly infinite rewrite sequences can be modeled using proof terms. Again, the foundation is a characterisation of projections for finitary rewriting described in [Terese. Term Rewriting Systems, volume 55 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, UK, 2003], Sec. 8.7. We extend this characterisation to infinitary rewriting and also refine it, by describing precisely the role that structural equivalence plays in the development of the notion of projection. The characterisation we propose yields a definite expression, i.e. a proof term, that describes the projection of an infinitary reduction over another. To illustrate the working of projections, we show how a common reduct of a (possibly infinite) reduction and a single step that makes part of it can be obtained via their respective projections. We show, by means of several examples, that the proposed definition yields the expected behavior also in cases beyond those covered by this result. Finally, we discuss how the notion of limit is used in our definition of projection for infinite reduction.",
keywords = "infinitary term rewriting, permutation equivalence, projection, proof terms",
author = "Carlos Lombardi and Alejandro R{\'i}os and {de Vrijer}, Roel",
year = "2017",
month = "6",
day = "11",
doi = "10.1016/j.entcs.2017.04.009",
language = "English",
volume = "332",
pages = "131--148",
journal = "Electronic Notes in Theoretical Computer Science",
issn = "1571-0661",
publisher = "Elsevier",

}

Projections for Infinitary Rewriting. / Lombardi, Carlos; Ríos, Alejandro; de Vrijer, Roel.

In: Electronic Notes in Theoretical Computer Science, Vol. 332, 11.06.2017, p. 131-148.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - Projections for Infinitary Rewriting

AU - Lombardi, Carlos

AU - Ríos, Alejandro

AU - de Vrijer, Roel

PY - 2017/6/11

Y1 - 2017/6/11

N2 - Proof terms in term rewriting are a representation means for reduction sequences, and more in general for contraction activity, allowing to distinguish e.g. simultaneous from sequential reduction. Proof terms for finitary, first-order, left-linear term rewriting are described in [Terese. Term Rewriting Systems, volume 55 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, UK, 2003], ch. 8. In a previous work [C. Lombardi, A. Ríos, and R. de Vrijer. Proof terms for infinitary rewriting. In G. Dowek, editor, RTA-TLCA'14, volume 8560 of Lecture Notes in Computer Science, pages 303–318. Springer, 2014] we defined an extension of the finitary proof-term formalism, that allows to describe contractions in infinitary first-order term rewriting, and gave a characterisation of permutation equivalence. In this work, we discuss how projections of possibly infinite rewrite sequences can be modeled using proof terms. Again, the foundation is a characterisation of projections for finitary rewriting described in [Terese. Term Rewriting Systems, volume 55 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, UK, 2003], Sec. 8.7. We extend this characterisation to infinitary rewriting and also refine it, by describing precisely the role that structural equivalence plays in the development of the notion of projection. The characterisation we propose yields a definite expression, i.e. a proof term, that describes the projection of an infinitary reduction over another. To illustrate the working of projections, we show how a common reduct of a (possibly infinite) reduction and a single step that makes part of it can be obtained via their respective projections. We show, by means of several examples, that the proposed definition yields the expected behavior also in cases beyond those covered by this result. Finally, we discuss how the notion of limit is used in our definition of projection for infinite reduction.

AB - Proof terms in term rewriting are a representation means for reduction sequences, and more in general for contraction activity, allowing to distinguish e.g. simultaneous from sequential reduction. Proof terms for finitary, first-order, left-linear term rewriting are described in [Terese. Term Rewriting Systems, volume 55 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, UK, 2003], ch. 8. In a previous work [C. Lombardi, A. Ríos, and R. de Vrijer. Proof terms for infinitary rewriting. In G. Dowek, editor, RTA-TLCA'14, volume 8560 of Lecture Notes in Computer Science, pages 303–318. Springer, 2014] we defined an extension of the finitary proof-term formalism, that allows to describe contractions in infinitary first-order term rewriting, and gave a characterisation of permutation equivalence. In this work, we discuss how projections of possibly infinite rewrite sequences can be modeled using proof terms. Again, the foundation is a characterisation of projections for finitary rewriting described in [Terese. Term Rewriting Systems, volume 55 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, Cambridge, UK, 2003], Sec. 8.7. We extend this characterisation to infinitary rewriting and also refine it, by describing precisely the role that structural equivalence plays in the development of the notion of projection. The characterisation we propose yields a definite expression, i.e. a proof term, that describes the projection of an infinitary reduction over another. To illustrate the working of projections, we show how a common reduct of a (possibly infinite) reduction and a single step that makes part of it can be obtained via their respective projections. We show, by means of several examples, that the proposed definition yields the expected behavior also in cases beyond those covered by this result. Finally, we discuss how the notion of limit is used in our definition of projection for infinite reduction.

KW - infinitary term rewriting

KW - permutation equivalence

KW - projection

KW - proof terms

UR - http://www.scopus.com/inward/record.url?scp=85021287660&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85021287660&partnerID=8YFLogxK

U2 - 10.1016/j.entcs.2017.04.009

DO - 10.1016/j.entcs.2017.04.009

M3 - Article

VL - 332

SP - 131

EP - 148

JO - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

SN - 1571-0661

ER -