{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:39:35Z","timestamp":1753889975884,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2007,5,15]],"date-time":"2007-05-15T00:00:00Z","timestamp":1179187200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/assumed-1991-2003"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We give a simple order-theoretic construction of a Cartesian closed category\nof sequential functions. It is based on bistable biorders, which are sets with\na partial order -- the extensional order -- and a bistable coherence, which\ncaptures equivalence of program behaviour, up to permutation of top (error) and\nbottom (divergence). We show that monotone and bistable functions (which are\nrequired to preserve bistably bounded meets and joins) are strongly sequential,\nand use this fact to prove universality results for the bistable biorder\nsemantics of the simply-typed lambda-calculus (with atomic constants), and an\nextension with arithmetic and recursion.\n  We also construct a bistable model of SPCF, a higher-order functional\nprogramming language with non-local control. We use our universality result for\nthe lambda-calculus to show that the semantics of SPCF is fully abstract. We\nthen establish a direct correspondence between bistable functions and\nsequential algorithms by showing that sequential data structures give rise to\nbistable biorders, and that each bistable function between such biorders is\ncomputed by a sequential algorithm.<\/jats:p>","DOI":"10.2168\/lmcs-3(2:5)2007","type":"journal-article","created":{"date-parts":[[2008,6,3]],"date-time":"2008-06-03T12:01:07Z","timestamp":1212494467000},"source":"Crossref","is-referenced-by-count":3,"title":["Bistable Biorders: A Sequential Domain Theory"],"prefix":"10.46298","volume":"Volume 3, Issue 2","author":[{"given":"James","family":"Laird","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2007,5,15]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/2222\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/2222\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:09:48Z","timestamp":1681243788000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/2222"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,5,15]]},"references-count":0,"URL":"https:\/\/doi.org\/10.2168\/lmcs-3(2:5)2007","relation":{"is-same-as":[{"id-type":"arxiv","id":"cs\/0702169","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.cs\/0702169","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2007,5,15]]},"article-number":"2222"}}