Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Severi, Paula; de Vries, Fer-Jan http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-34993
URL:

;

Meaningless Sets in Infinitary Combinatory Logic

pdf-format:


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 =		{http://dx.doi.org/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
Seminar: 23rd International Conference on Rewriting Techniques and Applications (RTA'12)
Issue date: 2012
Date of publication: 2012


DROPS-Home | Fulltext Search | Imprint Published by LZI