Bistability: an extensional characterization of sequentiality

James Laird

doi:10.1007/978-3-540-45220-1_30

Bistability: an extensional characterization of sequentiality

James Laird

Research output: Chapter or section in a book/report/conference proceeding › Book chapter

9 Citations (SciVal)

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 language	English
Title of host publication	Computer Science Logic
Subtitle of host publication	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
Editors	M. Baaz, J. A. Makowsky
Place of Publication	Berlin, Germany
Publisher	Springer Verlag
Pages	372-383
Number of pages	12
ISBN (Print)	9783540408017
DOIs	https://doi.org/10.1007/978-3-540-45220-1_30
Publication status	Published - 2003

Publication series

Name	Lecture Notes in Computer Science
Volume	2803

Access to Document

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

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

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). 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 or section in a book/report/conference proceeding › Book chapter

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). doi: 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 - Book chapter

AN - SCOPUS:35248892047

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 -

Bistability: an extensional characterization of sequentiality

Abstract

Publication series

Access to Document

Other files and links

Fingerprint

Cite this