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: https://drops.dagstuhl.de/opus/volltexte/2012/3499/
Severi, Paula ; de Vries, Fer-Jan
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 conditionsfor 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 | |
| Seminar: | 23rd International Conference on Rewriting Techniques and Applications (RTA'12) | |
| Issue date: | 2012 | |
| Date of publication: | 29.05.2012 |
