Projections for infinitary rewriting (extended version)

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 the literature. In a previous work, 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 modelled using proof terms. Again, the foundation is a characterisation of projections for finitary rewriting. 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 behaviour 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)92-110
Number of pages19
JournalTheoretical Computer Science
Volume781
DOIs
Publication statusPublished - 16 Aug 2019

Funding

This work was partially supported by the binational (France-Argentina) laboratory LIA INFINIS , and by the grants PUNQ-1258/13 and PUNQ 1439/15 of the Universidad Nacional de Quilmes , Argentina. We are grateful to the anonymous referees for their useful comments and suggestions. In particular, Subsection 5.1.1 was added to address one of their comments.

FundersFunder number
Universidad Nacional de QuilmesPUNQ-1258/13, PUNQ 1439/15

    Keywords

    • Infinitary term rewriting
    • Permutation equivalence
    • Projection
    • Proof terms

    Fingerprint

    Dive into the research topics of 'Projections for infinitary rewriting (extended version)'. Together they form a unique fingerprint.

    Cite this