Game semantics approach to higher-order complexity

DOI10.1016/J.JCSS.2017.02.003MaRDI QIDQ2396718zbMATHOpenAlexFDO

Authors Hugo Férée

Publication date 24 May 2017

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://kar.kent.ac.uk/64630/1/JCSS2017.pdf

zbMATH Keywords

BFFgame semanticsPCFhigher-order complexity

Mathematics Subject Classification ID

Applications of game theory (91A80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1342245
• Game semantics and the geometry of backtracking: a new complexity analysis of interaction
• An Application of Category-Theoretic Semantics to the Characterisation of Complexity Classes Using Higher-Order Function Algebras
• Game semantics for call-by-value polymorphism
• Games for complexity of second-order call-by-name programs

Cites work

• scientific article; zbMATH DE number 3163761 (Why is no real title available?)
• scientific article; zbMATH DE number 177794 (Why is no real title available?)
• scientific article; zbMATH DE number 1499102 (Why is no real title available?)
• scientific article; zbMATH DE number 806755 (Why is no real title available?)
• scientific article; zbMATH DE number 2204752 (Why is no real title available?)
• scientific article; zbMATH DE number 3305097 (Why is no real title available?)
• A new Characterization of Type-2 Feasibility
• Adventures in time and space
• Analytical properties of resource-bounded real functionals
• Complexity theory for operators in analysis
• Derivational complexity is an invariant cost model
• Freshness and Name-Restriction in Sets of Traces with Names
• Functional interpretations of feasibly constructive arithmetic
• Game semantics in the nominal model
• LCF considered as a programming language
• On characterizations of the basic feasible functionals. I
• On full abstraction for PCF: I, II and III
• On the query complexity of real functionals
• Polynomial and abstract subrecursive classes
• Resource-bounded continuity and sequentiality for type-two functionals

Cited in

(8)

• A game-semantic model of computation
• Finite high-order games and an inductive approach towards Gowers's dichotomy
• Game Semantics in String Diagrams
• Game semantics and the geometry of backtracking: a new complexity analysis of interaction
• Quantitative continuity and Computable Analysis in Coq
• Games for complexity of second-order call-by-name programs
• On higher-order reachability games vs may reachability
• A Game Semantics of Idealized CSP

This page was built for publication: Game semantics approach to higher-order complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2396718)