F. Aschieri:
"Game semantics and the geometry of backtracking: a new complexity analysis and interaction";
Journal of Symbolic Logic, 82 (2017), 2; S. 672 - 708.

Kurzfassung englisch:
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.

Game semantics and the geometry of backtracking: A new complexity analysis of... | Request PDF. Available from: https://www.researchgate.net/publication/317666958_Game_semantics_and_the_geometry_of_backtracking_A_new_complexity_analysis_of_interaction [accessed Jan 15 2018].

"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)

Erstellt aus der Publikationsdatenbank der Technischen Universitšt Wien.