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 or section

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 -