Meaningless Sets in Infinitary Combinatory Logic

Authors Paula Severi, Fer-Jan de Vries



PDF
Thumbnail PDF

File

LIPIcs.RTA.2012.288.pdf
  • Filesize: 484 kB
  • 17 pages

Document Identifiers

Author Details

Paula Severi
Fer-Jan de Vries

Cite AsGet BibTex

Paula Severi and Fer-Jan de Vries. Meaningless Sets in Infinitary Combinatory Logic. In 23rd International Conference on Rewriting Techniques and Applications (RTA'12). Leibniz International Proceedings in Informatics (LIPIcs), Volume 15, pp. 288-304, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.RTA.2012.288

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.
Keywords
  • Infinitary Rewriting
  • Combinatory Logic
  • Meaningless Sets
  • Confluence
  • Normalisation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail