Polynat in PER models

DOI10.1016/J.TCS.2004.01.031MaRDI QIDQ1434360zbMATH OpenOpenAlexFDO

Authors Ivar Rummelhoff

Publication date 4 August 2004

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2004.01.031

zbMATH Keywords

PERPolymorphismSemanticsType theory

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Abstract data types; algebraic specification (68Q65)

Review text

So-called PERs, partial equivalence relations (symmetric and transitive) applied on a partial combinatory algebra (combinators K and S with the standard but partial combinatorial interpretations), form a model for polymorphically typed lambda-calculus (system F). The polymorphic natural number type N (polynat) is used to uniquely represent numbers by (polymorphic) Church numerals. It is shown that the type N is not always polymorphically standard in the PER-model, meaning that the interpretation of the type N contains not only interpretations of the Church numerals. An explicit counterexample is constructed. The paper is well written but too short and too technical to be self-contained. It requires from the reader much deeper introductory study of the subject.

Recommendations

• scientific article; zbMATH DE number 3882404
• scientific article; zbMATH DE number 19052
• Algebraic types in PER models
• scientific article; zbMATH DE number 1670474
• Extensional models for polymorphism

Cites work

• Algebraic types in PER models
• Automatic synthesis of typed -programs on term algebras
• scientific article; zbMATH DE number 3900744 (Why is no real title available?)
• scientific article; zbMATH DE number 4103058 (Why is no real title available?)
• scientific article; zbMATH DE number 512792 (Why is no real title available?)

Cited in

(6)

• scientific article; zbMATH DE number 1670474 (Why is no real title available?)
• scientific article; zbMATH DE number 4181330 (Why is no real title available?)
• scientific article; zbMATH DE number 4154448 (Why is no real title available?)
• Polya Urn Models
• scientific article; zbMATH DE number 4103058 (Why is no real title available?)
• Algebraic types in PER models

This page was built for publication: Polynat in PER models

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1434360)