Extensional PERs

DOI10.1016/0890-5401(92)90019-CMaRDI QIDQ1193589zbMATH OpenFDO

Authors S. Singh

Publication date 27 September 1992

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(92)90019-C

zbMATH Keywords

Cartesian closed categorycategory of domainspartial equivalence relationssemantics of programming languagesTuring machines

Mathematics Subject Classification ID

Categories of spans/cospans, relations, or partial maps (18B10) Topoi (18B25) Closed categories (closed monoidal and Cartesian closed categories, etc.) (18D15) Semantics in the theory of computing (68Q55)

Review text

Mathematical (denotational) semantics of programming languages requires a general framework supporting computational models and effectiveness. Searching for a good category of domains, the authors present results on a class of Partial Equivalence Relations (PERs) on natural numbers. Extensional PER (ExPER for short) is a Cartesian closed category where every endomorphism has a canonical fixed point. Domain equations are guaranteed to have solutions because all basic functors are realizable and have canonical invariant objects. The notions which appear in the paper related to the category (Ex)PER are defined using familiar tools from computation theory, namely Turing machines.

Recommendations

• scientific article; zbMATH DE number 4181330
• A note on ``Extensional PERs
• Building domains from graph models
• From term models to domains
• scientific article; zbMATH DE number 956835

Cites work

• Generalized Banach-Mazur functionals in the topos of recursive sets
• scientific article; zbMATH DE number 3825806 (Why is no real title available?)
• scientific article; zbMATH DE number 4061468 (Why is no real title available?)
• scientific article; zbMATH DE number 48157 (Why is no real title available?)

Cited in

(17)

• Inheritance as implicit coercion
• Monads and algebras in the semantics of partial data types
• Some economic applications of Scott domains
• Independence of the induction principle and the axiom of choice in the pure calculus of constructions
• Partial map classifiers and partial cartesian closed categories
• A new framework for declarative programming
• Computational adequacy for recursive types in models of intuitionistic set theory
• scientific article; zbMATH DE number 4181330 (Why is no real title available?)
• scientific article; zbMATH DE number 4103058 (Why is no real title available?)
• Building domains from graph models
• From term models to domains
• Lifting theorems for Kleisli categories
• Domains in \(H\)
• An exper model for Quest
• A note on ``Extensional PERs
• Synthetic domain theory in type theory: another logic of computable functions
• A note on logical PERs and reducibility. Logical relations strike again!

This page was built for publication: Extensional PERs

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