2015/11/19 by Federico Aschieri, Aschieri, Federico
Computer Science · Decision Sciences · #Artificial Intelligence in Games #Computability, Logic, AI Algorithms #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Logic (math.LO) #Logic in Computer Science (cs.LO)
paper · pdf · doi:10.48550/arxiv.1511.06260
openalex publication_date 2015/11/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present abstract complexity results about Coquand and Hyland-Ong game\nsemantics, that will lead to new bounds on the length of first-order\ncut-elimination, normalization, interaction between expansion trees and any\nother dialogical process game semantics can model and apply to. In particular,\nwe provide a novel method to bound the length of interactions between visible\nstrategies and to measure precisely the tower of exponentials defining the\nworst-case complexity. Our study improves the old estimates on average by\nseveral exponentials.\n