Game semantics approach to higher-order complexity

Férée, Hugo (2017) Game semantics approach to higher-order complexity. Journal of Computer and System Sciences, 87 . pp. 1-15. ISSN 0022-0000. (doi:https://doi.org/10.1016/j.jcss.2017.02.003) (Full text available)

Abstract

Game semantics was initially defined and used to characterize pcf functionals. We use this approach to propose a definition of complexity for such higher-order functions, as well as a class of polynomial time computable higher-order functions.

Item Type: Article
Uncontrolled keywords: Higher-order Complexity Game semantics bff pcf
Subjects: Q Science > QA Mathematics (inc Computing science) > QA 9 Formal systems, logics
Divisions: Faculties > Sciences > School of Computing
Faculties > Sciences > School of Computing > Programming Languages and Systems Group
Depositing User: Hugo Feree
Date Deposited: 22 Nov 2017 16:24 UTC
Last Modified: 09 Aug 2018 11:18 UTC
Resource URI: https://kar.kent.ac.uk/id/eprint/64630 (The current URI for this page, for reference purposes)
  • Depositors only (login required):

Downloads

Downloads per month over past year