Sequentiality in bounded biorders

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

We study a notion of bounded stable biorder, showing that the monotone and stable functions on such biorders are sequential. We construct bounded biorder models of a range of sequential, higher-order functional calculi, including unary PCF, (typed and untyped) call-by-value and lazy λ-calculi, and non-deterministic SPCF. We prove universality and full abstraction results for these models by reduction to the case of unary PCF, for which we give a simple new argument to show that any order-extensional and sequential model is universal.

Original languageEnglish
Pages (from-to)173-191
Number of pages19
JournalFundamenta Informaticae
Volume65
Issue number1-2
Publication statusPublished - 2005

Fingerprint

Unary
Functional Calculus
Lambda Calculus
Universality
Monotone
Model
Higher Order
Range of data
Abstraction

Cite this

Sequentiality in bounded biorders. / Laird, James.

In: Fundamenta Informaticae, Vol. 65, No. 1-2, 2005, p. 173-191.

Research output: Contribution to journalArticle

Laird, J 2005, 'Sequentiality in bounded biorders', Fundamenta Informaticae, vol. 65, no. 1-2, pp. 173-191.
Laird, James. / Sequentiality in bounded biorders. In: Fundamenta Informaticae. 2005 ; Vol. 65, No. 1-2. pp. 173-191.
@article{7a1291ee398f4a24afa92908a3d24b96,
title = "Sequentiality in bounded biorders",
abstract = "We study a notion of bounded stable biorder, showing that the monotone and stable functions on such biorders are sequential. We construct bounded biorder models of a range of sequential, higher-order functional calculi, including unary PCF, (typed and untyped) call-by-value and lazy λ-calculi, and non-deterministic SPCF. We prove universality and full abstraction results for these models by reduction to the case of unary PCF, for which we give a simple new argument to show that any order-extensional and sequential model is universal.",
author = "James Laird",
year = "2005",
language = "English",
volume = "65",
pages = "173--191",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
publisher = "IOS Press",
number = "1-2",

}

TY - JOUR

T1 - Sequentiality in bounded biorders

AU - Laird, James

PY - 2005

Y1 - 2005

N2 - We study a notion of bounded stable biorder, showing that the monotone and stable functions on such biorders are sequential. We construct bounded biorder models of a range of sequential, higher-order functional calculi, including unary PCF, (typed and untyped) call-by-value and lazy λ-calculi, and non-deterministic SPCF. We prove universality and full abstraction results for these models by reduction to the case of unary PCF, for which we give a simple new argument to show that any order-extensional and sequential model is universal.

AB - We study a notion of bounded stable biorder, showing that the monotone and stable functions on such biorders are sequential. We construct bounded biorder models of a range of sequential, higher-order functional calculi, including unary PCF, (typed and untyped) call-by-value and lazy λ-calculi, and non-deterministic SPCF. We prove universality and full abstraction results for these models by reduction to the case of unary PCF, for which we give a simple new argument to show that any order-extensional and sequential model is universal.

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

UR - http://content.iospress.com/articles/fundamenta-informaticae/fi65-1-2-09

M3 - Article

VL - 65

SP - 173

EP - 191

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 1-2

ER -