Asynchronous games: innocence without alternation

Abstract : The notion of innocent strategy was introduced by Hyland and Ong in order to capture the interactive behaviour of lambda-terms and PCF programs. An innocent strategy is defined as an alternating strategy with partial memory, in which the strategy plays according to its view. Extending the definition to non-alternating strategies is problematic, because the traditional definition of views is based on the hypothesis that Opponent and Proponent alternate during the interaction. Here, we take advantage of the diagrammatic reformulation of alternating innocence in asynchronous games, in order to provide a tentative definition of innocence in non-alternating games. The task is interesting, and far from easy. It requires the combination of true concurrency and game semantics in a clean and organic way, clarifying the relationship between asynchronous games and concurrent games in the sense of Abramsky and Melliès. It also requires an interactive reformulation of the usual acyclicity criterion of linear logic, as well as a directed variant, as a scheduling criterion.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00152707
Contributor : Samuel Mimram <>
Submitted on : Thursday, June 7, 2007 - 1:17:46 PM
Last modification on : Friday, January 4, 2019 - 5:32:59 PM
Long-term archiving on : Thursday, April 8, 2010 - 5:14:07 PM

Files

concur07.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00152707, version 1
  • ARXIV : 0706.1118

Collections

Citation

Paul-André Melliès, Samuel Mimram. Asynchronous games: innocence without alternation. 2007. ⟨hal-00152707⟩

Share

Metrics

Record views

186

Files downloads

147