Games characterizing Levy-Longo trees

DOI10.1016/S0304-3975(03)00405-5MaRDI QIDQ1884875zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 27 October 2004

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(03)00405-5

zbMATH Keywords

arenasfull abstractiongame semanticsLambda calculusuniversality

Mathematics Subject Classification ID

Combinatory logic and lambda calculus (03B40) Semantics in the theory of computing (68Q55) Other game-theoretic models (91A40)

Review text

A simple \textit{strongly universal} innocent game model for Lévy-Longo trees is presented: every point in the model is the denotation of a unique Lévy-Longo tree. The observational quotient of the model then gives a universal, and hence fully abstract, model of the pure Lazy Lambda Calculus.

Recommendations

• scientific article; zbMATH DE number 2086645
• Publication:4945241
• Adapting innocent game models for the Böhm tree \(\lambda\)-theory
• scientific article; zbMATH DE number 2080222
• Innocent game models of untyped -calculus

Cites work

• Call-by-name, call-by-value and the \(\lambda\)-calculus
• Full abstraction for PCF
• Full abstraction in the lazy lambda calculus
• scientific article; zbMATH DE number 1722650 (Why is no real title available?)
• scientific article; zbMATH DE number 3875232 (Why is no real title available?)
• scientific article; zbMATH DE number 3523519 (Why is no real title available?)
• scientific article; zbMATH DE number 1342276 (Why is no real title available?)
• scientific article; zbMATH DE number 1841820 (Why is no real title available?)
• scientific article; zbMATH DE number 1424050 (Why is no real title available?)
• Innocent game models of untyped -calculus
• On full abstraction for PCF: I, II and III
• Set-theoretical models of lambda-calculus: theories, expansions, isomorphisms

Cited in

(6)

• Trees and Ehrenfeucht-Fraïssé games
• The eigen-distribution of weighted game trees
• Eager functions as processes
• scientific article; zbMATH DE number 1722650 (Why is no real title available?)
• scientific article; zbMATH DE number 2086645 (Why is no real title available?)
• Extensional and non-extensional functions as processes

This page was built for publication: Games characterizing Levy-Longo trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1884875)