### 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 | |

Publication status | Published - 2003 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 2803 |

### Fingerprint

### Cite this

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

Research output: Chapter in Book/Report/Conference proceeding › Chapter

*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

}

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 -