Estimation of the length of interactions in arena game semantics

Pierre Clairambault

Research output: Chapter in Book/Report/Conference proceedingChapter

6 Citations (Scopus)

Abstract

We estimate the maximal length of interactions between strategies in HO/N game semantics, in the spirit of the work by Schwichtenberg and Beckmann for the length of reduction in simply typed λ-calculus. Because of the operational content of game semantics, the bounds presented here also apply to head linear reduction on λ-terms and to the execution of programs by abstract machines (PAM/KAM), including in presence of computational effects such as non-determinism or ground type references. The proof proceeds by extracting from the games model a combinatorial rewriting rule on trees of natural numbers, which can then be analysed independently of game semantics or λ-calculus.
Original languageEnglish
Title of host publicationFoundations of Software Science and Computational Structures - 14th Int. Conf., FOSSACS 2011, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2011, Proceedings
Place of PublicationHeidelberg
PublisherSpringer
Pages335-349
Number of pages15
Volume6604 LNCS
ISBN (Print)03029743
DOIs
Publication statusPublished - 2011
Event14th International Conference on Foundations of Software Science and Computational Structures, FOSSACS 2011, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2011, March 26, 2010 - April 3, 2010 - Saarbrucken, Germany
Duration: 1 Jan 2011 → …

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag

Conference

Conference14th International Conference on Foundations of Software Science and Computational Structures, FOSSACS 2011, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2011, March 26, 2010 - April 3, 2010
CountryGermany
CitySaarbrucken
Period1/01/11 → …

    Fingerprint

Cite this

Clairambault, P. (2011). Estimation of the length of interactions in arena game semantics. In Foundations of Software Science and Computational Structures - 14th Int. Conf., FOSSACS 2011, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2011, Proceedings (Vol. 6604 LNCS, pp. 335-349). (Lecture Notes in Computer Science). Heidelberg: Springer. https://doi.org/10.1007/978-3-642-19805-2_23