Estimation of the length of interactions in arena game semantics

Pierre Clairambault

doi:10.1007/978-3-642-19805-2_23

Estimation of the length of interactions in arena game semantics

Pierre Clairambault

Department of Computer Science

Research output: Chapter or section in a book/report/conference proceeding › Chapter or section

9 Citations (SciVal)

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 language	English
Title of host publication	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
Place of Publication	Heidelberg
Publisher	Springer
Pages	335-349
Number of pages	15
Volume	6604 LNCS
ISBN (Print)	03029743
DOIs	https://doi.org/10.1007/978-3-642-19805-2_23
Publication status	Published - 2011
Event	14th 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

Name	Lecture Notes in Computer Science
Publisher	Springer Verlag

Conference

Conference	14th 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
Country/Territory	Germany
City	Saarbrucken
Period	1/01/11 → …

Access to Document

10.1007/978-3-642-19805-2_23

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). Springer. https://doi.org/10.1007/978-3-642-19805-2_23

Estimation of the length of interactions in arena game semantics. / Clairambault, Pierre.
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 Heidelberg: Springer, 2011. p. 335-349 (Lecture Notes in Computer Science).

Research output: Chapter or section in a book/report/conference proceeding › Chapter or section

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, Lecture Notes in Computer Science, Springer, Heidelberg, pp. 335-349, 14th 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, 1/01/11. https://doi.org/10.1007/978-3-642-19805-2_23

Clairambault P. 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. Heidelberg: Springer. 2011. p. 335-349. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-19805-2_23

Clairambault, Pierre. / Estimation of the length of interactions in arena game semantics. 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 Heidelberg : Springer, 2011. pp. 335-349 (Lecture Notes in Computer Science).

@inbook{082efa79488246828c1e51087a92984f,

title = "Estimation of the length of interactions in arena game semantics",

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.",

author = "Pierre Clairambault",

year = "2011",

doi = "10.1007/978-3-642-19805-2_23",

language = "English",

isbn = "03029743",

volume = "6604 LNCS",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "335--349",

booktitle = "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",

note = "14th 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 ; Conference date: 01-01-2011",

}

TY - CHAP

T1 - Estimation of the length of interactions in arena game semantics

AU - Clairambault, Pierre

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

UR - http://dx.doi.org/10.1007/978-3-642-19805-2_23

U2 - 10.1007/978-3-642-19805-2_23

DO - 10.1007/978-3-642-19805-2_23

M3 - Chapter or section

SN - 03029743

VL - 6604 LNCS

T3 - Lecture Notes in Computer Science

SP - 335

EP - 349

BT - 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

PB - Springer

CY - Heidelberg

T2 - 14th 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

Y2 - 1 January 2011

ER -

Estimation of the length of interactions in arena game semantics

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this