Hostname: page-component-7b7567c8c-p67k6 Total loading time: 0 Render date: 2026-11-19T18:21:41.687Z Has data issue: false hasContentIssue false

GAME SEMANTICS AND THE GEOMETRY OF BACKTRACKING: A NEW COMPLEXITY ANALYSIS OF INTERACTION

Published online by Cambridge University Press:  19 June 2017

FEDERICO ASCHIERI*
Affiliation:
INSTITUT FÜR DISKRETE MATHEMATIK UND GEOMETRIE TECHNISCHE UNIVERSITÄT WIEN WIEDNER HAUPTSTRAßE 8-10/104, 1040 VIENNA, AUSTRIA E-mail: federico.aschieri@tuwien.ac.at
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We present abstract complexity results about Coquand and Hyland–Ong game semantics, that will lead to new bounds on the length of first-order cut-elimination, normalization, interaction between expansion trees and any other dialogical process game semantics can model and apply to. In particular, we provide a novel method to bound the length of interactions between visible strategies and to measure precisely the tower of exponentials defining the worst-case complexity. Our study improves the old estimates on average by several exponentials.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2017