Zeitschriftenartikel:
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)
http://dx.doi.org/10.1017/jsl.2016.48
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.