The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.RTA.2012.288
URN: urn:nbn:de:0030-drops-34993
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3499/
Go to the corresponding LIPIcs Volume Portal

Severi, Paula ; de Vries, Fer-Jan

Meaningless Sets in Infinitary Combinatory Logic

pdf-format:
22.pdf (0.5 MB)

Abstract

In this paper we study meaningless sets in infinitary combinatory logic. So far only a handful of meaningless sets were known. We show that there are uncountably many meaningless sets. As an application to the semantics of finite combinatory logics, we show that there exist uncountably many combinatory algebras that are not a lambda algebra. We also study ways of weakening the axioms of meaningless sets to get, not only sufficient, but also necessary conditions
for having confluence and normalisation.

BibTeX - Entry

@InProceedings{severi_et_al:LIPIcs:2012:3499,
  author =	{Paula Severi and Fer-Jan de Vries},
  title =	{{Meaningless Sets in Infinitary Combinatory Logic}},
  booktitle =	{23rd International Conference on Rewriting Techniques and Applications (RTA'12) },
  pages =	{288--304},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-38-5},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{15},
  editor =	{Ashish Tiwari},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3499},
  URN =		{urn:nbn:de:0030-drops-34993},
  doi =		{10.4230/LIPIcs.RTA.2012.288},
  annote =	{Keywords: Infinitary Rewriting, Combinatory Logic,  Meaningless Sets, Confluence, Normalisation}
}

Keywords: Infinitary Rewriting, Combinatory Logic, Meaningless Sets, Confluence, Normalisation
Collection: 23rd International Conference on Rewriting Techniques and Applications (RTA'12)
Issue Date: 2012
Date of publication: 29.05.2012

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