The sequentially realizable functionals

DOI10.1016/S0168-0072(01)00110-5zbMath1022.03023OpenAlexW1985955425MaRDI QIDQ1849853

John Longley

Publication date: 2 December 2002

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0168-0072(01)00110-5

zbMATH Keywords

realizabilitystrong stabilityPCFsequentialityfinite type structureshigher-type computability

Mathematics Subject Classification ID

Semantics in the theory of computing (68Q55) Theory of numerations, effectively presented structures (03D45) Combinatory logic and lambda calculus (03B40) Higher-type and set recursion theory (03D65)

Related Items

Comparing hierarchies of types in models of linear logic ⋮ A synthetic theory of sequential domains ⋮ Unnamed Item ⋮ On the reification of semantic linearity ⋮ A stable programming language ⋮ On the ubiquity of certain total type structures ⋮ Some Programming Languages Suggested by Game Models (Extended Abstract) ⋮ Unnamed Item ⋮ Non-uniform (hyper/multi)coherence spaces ⋮ Continuous and monotone machines ⋮ Computing with Functionals—Computability Theory or Computer Science? ⋮ On the computational complexity of Longley's \(H\) functional ⋮ Non-Uniform Hypercoherences ⋮ Axioms and (counter)examples in synthetic domain theory ⋮ Parallel and serial hypercoherences ⋮ Sequential algorithms and strongly stable functions ⋮ A relative PCF-definability result for strongly stable functions and some corollaries ⋮ Definability and Full Abstraction

Uses Software

• ML

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The modified realizability topos
• The lambda calculus. Its syntax and semantics. Rev. ed.
• A small complete category
• Generalized Banach-Mazur functionals in the topos of recursive sets
• Sequential algorithms on concrete data structures
• Sheaves in geometry and logic: a first introduction to topos theory
• LCF considered as a programming language
• Fully abstract models of typed \(\lambda\)-calculi
• Concrete domains
• A type-theoretical alternative to ISWIM, CUCH, OWHY
• Sequentiality in an extensional framework
• Fully abstract semantics for observably sequential languages
• On the computational complexity of Longley's \(H\) functional
• A relative PCF-definability result for strongly stable functions and some corollaries
• On full abstraction for PCF: I, II and III
• Full abstraction for PCF
• Kripke logical relations and PCF
• Projecting sequential algorithms on strongly stable functions
• When is a functional program not a functional program?
• Data Types as Lattices
• Full abstraction, totality and PCF
• Localisation and interaction in one dimension
• Fully abstract translations between functional languages
• A uniform approach to domain theory in realizability models
• Finitary PCF is not decidable