License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TYPES.2011.16
URN: urn:nbn:de:0030-drops-38971
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3897/
Go to the corresponding LIPIcs Volume Portal

Endrullis, Jörg ; Polonsky, Andrew

Infinitary Rewriting Coinductively

pdf-format:
3.pdf (0.5 MB)

Abstract

We provide a coinductive definition of strongly convergent reductions between infinite lambda terms. This approach avoids the notions of ordinals and metric convergence which have appeared in the earlier definitions of the concept. As an illustration, we prove the existence part of the infinitary standardization theorem. The proof is fully formalized in Coq using coinductive types. The paper concludes with a characterization of infinite lambda terms which reduce to themselves in a single beta step.

BibTeX - Entry

@InProceedings{endrullis_et_al:LIPIcs:2013:3897,
  author =	{J{\"o}rg Endrullis and Andrew Polonsky},
  title =	{{Infinitary Rewriting Coinductively}},
  booktitle =	{18th International Workshop on Types for Proofs and Programs (TYPES 2011)},
  pages =	{16--27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-49-1},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{19},
  editor =	{Nils Anders Danielsson and Bengt Nordstr{\"o}m},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/3897},
  URN =		{urn:nbn:de:0030-drops-38971},
  doi =		{10.4230/LIPIcs.TYPES.2011.16},
  annote =	{Keywords: infinitary rewriting,  coinduction,  lambda calculus,  standardization }
}

Keywords: infinitary rewriting, coinduction, lambda calculus, standardization
Collection: 18th International Workshop on Types for Proofs and Programs (TYPES 2011)
Issue Date: 2013
Date of publication: 21.01.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI