Bistability: an extensional characterization of sequentiality

Research output: Chapter in Book/Report/Conference proceedingChapter

9 Citations (Scopus)

Abstract

We give a simple order-theoretic construction of a cartesian closed category of sequential functions. It is based on biordered sets analogous to Berry's bidomains, except that the stable order is replaced with a new notion, the bistable order, and instead of preserving stably bounded greatest lower bounds, functions are required to preserve bistably bounded least upper bounds and greatest lower bounds. We show that bistable epos and bistable and continuous functions form a CCC, yielding models of functional languages such as the simply-typed λ-calculus and SPCF. We show that these models are strongly sequential and use this fact to prove universality and full abstraction results.

Original languageEnglish
Title of host publicationComputer Science Logic
Subtitle of host publicationProceedings of 17th International Workshop CSL 2003, 12th Annual Conference of the (EACSL), 8th Kurt Gödel Colloquium, KGC 2003, Vienna, Austria, August 25-30, 2003
EditorsM. Baaz, J. A. Makowsky
Place of PublicationBerlin, Germany
PublisherSpringer Verlag
Pages372-383
Number of pages12
ISBN (Print)9783540408017
DOIs
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science
Volume2803

Fingerprint Dive into the research topics of 'Bistability: an extensional characterization of sequentiality'. Together they form a unique fingerprint.

Cite this