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

Bistability
Cartesian Closed Category
Lower bound
Typed lambda Calculus
Universality
Continuous Function
Upper bound
Model

Cite this

Laird, J. (2003). Bistability: an extensional characterization of sequentiality. In M. Baaz, & J. A. Makowsky (Eds.), Computer Science Logic: Proceedings 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 (pp. 372-383). (Lecture Notes in Computer Science; Vol. 2803). Berlin, Germany: Springer Verlag. https://doi.org/10.1007/978-3-540-45220-1_30

Bistability : an extensional characterization of sequentiality. / Laird, James.

Computer Science Logic: Proceedings 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. ed. / M. Baaz; J. A. Makowsky. Berlin, Germany : Springer Verlag, 2003. p. 372-383 (Lecture Notes in Computer Science; Vol. 2803).

Research output: Chapter in Book/Report/Conference proceedingChapter

Laird, J 2003, Bistability: an extensional characterization of sequentiality. in M Baaz & JA Makowsky (eds), Computer Science Logic: Proceedings 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. Lecture Notes in Computer Science, vol. 2803, Springer Verlag, Berlin, Germany, pp. 372-383. https://doi.org/10.1007/978-3-540-45220-1_30
Laird J. Bistability: an extensional characterization of sequentiality. In Baaz M, Makowsky JA, editors, Computer Science Logic: Proceedings 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. Berlin, Germany: Springer Verlag. 2003. p. 372-383. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-540-45220-1_30
Laird, James. / Bistability : an extensional characterization of sequentiality. Computer Science Logic: Proceedings 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. editor / M. Baaz ; J. A. Makowsky. Berlin, Germany : Springer Verlag, 2003. pp. 372-383 (Lecture Notes in Computer Science).
@inbook{3e6430ff74264bc490b40a519f845bfe,
title = "Bistability: an extensional characterization of sequentiality",
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.",
author = "James Laird",
year = "2003",
doi = "10.1007/978-3-540-45220-1_30",
language = "English",
isbn = "9783540408017",
series = "Lecture Notes in Computer Science",
publisher = "Springer Verlag",
pages = "372--383",
editor = "M. Baaz and Makowsky, {J. A.}",
booktitle = "Computer Science Logic",

}

TY - CHAP

T1 - Bistability

T2 - an extensional characterization of sequentiality

AU - Laird, James

PY - 2003

Y1 - 2003

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=35248892047&partnerID=8YFLogxK

UR - http://dx.doi.org/10.1007/978-3-540-45220-1_30

U2 - 10.1007/978-3-540-45220-1_30

DO - 10.1007/978-3-540-45220-1_30

M3 - Chapter

SN - 9783540408017

T3 - Lecture Notes in Computer Science

SP - 372

EP - 383

BT - Computer Science Logic

A2 - Baaz, M.

A2 - Makowsky, J. A.

PB - Springer Verlag

CY - Berlin, Germany

ER -