Reinterpreting Compression in Infinitary Rewriting

J. Ketema

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)
18 Downloads (Pure)

Abstract

Departing from a computational interpretation of compression in infinitary rewriting, we view compression as a degenerate case of standardisation. The change in perspective comes about via two observations: (a) no compression property can be recovered for non-left-linear systems and (b) some standardisation procedures, as a ‘side-effect’, yield compressed reductions.
Original languageUndefined
Title of host publicationProceedings of the 23rd International Conference on Rewriting Techniques and Applications (RTA 2012)
EditorsAshish Tiwari
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Pages209-224
Number of pages16
ISBN (Print)978-3-939897-38-5
DOIs
Publication statusPublished - May 2012

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume15
ISSN (Print)1868-8969

Keywords

  • IR-80543
  • METIS-287874
  • Infinitary Rewriting
  • standardisation
  • EWI-21865
  • Term rewriting
  • CR-F.1.1
  • CR-F.3.2
  • CR-F.4.2
  • compression

Cite this

Ketema, J. (2012). Reinterpreting Compression in Infinitary Rewriting. In A. Tiwari (Ed.), Proceedings of the 23rd International Conference on Rewriting Techniques and Applications (RTA 2012) (pp. 209-224). (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 15). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. https://doi.org/10.4230/LIPIcs.RTA.2012.209
Ketema, J. / Reinterpreting Compression in Infinitary Rewriting. Proceedings of the 23rd International Conference on Rewriting Techniques and Applications (RTA 2012). editor / Ashish Tiwari. Dagstuhl, Germany : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2012. pp. 209-224 (Leibniz International Proceedings in Informatics (LIPIcs)).
@inproceedings{3e8c08544bd64e7b8bf664d240479cff,
title = "Reinterpreting Compression in Infinitary Rewriting",
abstract = "Departing from a computational interpretation of compression in infinitary rewriting, we view compression as a degenerate case of standardisation. The change in perspective comes about via two observations: (a) no compression property can be recovered for non-left-linear systems and (b) some standardisation procedures, as a ‘side-effect’, yield compressed reductions.",
keywords = "IR-80543, METIS-287874, Infinitary Rewriting, standardisation, EWI-21865, Term rewriting, CR-F.1.1, CR-F.3.2, CR-F.4.2, compression",
author = "J. Ketema",
note = "10.4230/LIPIcs.RTA.2012.209",
year = "2012",
month = "5",
doi = "10.4230/LIPIcs.RTA.2012.209",
language = "Undefined",
isbn = "978-3-939897-38-5",
series = "Leibniz International Proceedings in Informatics (LIPIcs)",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik",
pages = "209--224",
editor = "Ashish Tiwari",
booktitle = "Proceedings of the 23rd International Conference on Rewriting Techniques and Applications (RTA 2012)",
address = "Germany",

}

Ketema, J 2012, Reinterpreting Compression in Infinitary Rewriting. in A Tiwari (ed.), Proceedings of the 23rd International Conference on Rewriting Techniques and Applications (RTA 2012). Leibniz International Proceedings in Informatics (LIPIcs), vol. 15, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, pp. 209-224. https://doi.org/10.4230/LIPIcs.RTA.2012.209

Reinterpreting Compression in Infinitary Rewriting. / Ketema, J.

Proceedings of the 23rd International Conference on Rewriting Techniques and Applications (RTA 2012). ed. / Ashish Tiwari. Dagstuhl, Germany : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2012. p. 209-224 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 15).

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Reinterpreting Compression in Infinitary Rewriting

AU - Ketema, J.

N1 - 10.4230/LIPIcs.RTA.2012.209

PY - 2012/5

Y1 - 2012/5

N2 - Departing from a computational interpretation of compression in infinitary rewriting, we view compression as a degenerate case of standardisation. The change in perspective comes about via two observations: (a) no compression property can be recovered for non-left-linear systems and (b) some standardisation procedures, as a ‘side-effect’, yield compressed reductions.

AB - Departing from a computational interpretation of compression in infinitary rewriting, we view compression as a degenerate case of standardisation. The change in perspective comes about via two observations: (a) no compression property can be recovered for non-left-linear systems and (b) some standardisation procedures, as a ‘side-effect’, yield compressed reductions.

KW - IR-80543

KW - METIS-287874

KW - Infinitary Rewriting

KW - standardisation

KW - EWI-21865

KW - Term rewriting

KW - CR-F.1.1

KW - CR-F.3.2

KW - CR-F.4.2

KW - compression

U2 - 10.4230/LIPIcs.RTA.2012.209

DO - 10.4230/LIPIcs.RTA.2012.209

M3 - Conference contribution

SN - 978-3-939897-38-5

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 209

EP - 224

BT - Proceedings of the 23rd International Conference on Rewriting Techniques and Applications (RTA 2012)

A2 - Tiwari, Ashish

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

CY - Dagstuhl, Germany

ER -

Ketema J. Reinterpreting Compression in Infinitary Rewriting. In Tiwari A, editor, Proceedings of the 23rd International Conference on Rewriting Techniques and Applications (RTA 2012). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. 2012. p. 209-224. (Leibniz International Proceedings in Informatics (LIPIcs)). https://doi.org/10.4230/LIPIcs.RTA.2012.209