Game semantics for dependent types

被引:2
作者
Vakar, Matthijs [1 ]
Jagadeesan, Radha [2 ]
Abramsky, Samson [1 ]
机构
[1] Univ Oxford, Dept Comp Sci, Wolfson Bldg,Parks Rd, Oxford OX1 3QD, England
[2] Depaul Univ, Sch CTI, 243 S Wabash Ave, Chicago, IL 60604 USA
基金
英国工程与自然科学研究理事会;
关键词
Game semantics; Dependent type theory; Intensionality; FULL ABSTRACTION; COMPLETENESS; LOGIC; PCF;
D O I
10.1016/j.ic.2018.02.015
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We present a model of dependent type theory (DTT) with Pi-, 1-, Sigma-and intensional Id-types, which is based on a slight variation of the (call-by-name) category of AJM-games and history-free winning well-bracketed strategies. The model satisfies Streicher's criteria of intensionality and refutes function extensionality. The principle of uniqueness of identity proofs is satisfied. We show it contains a submodel as a full subcategory which gives a faithful interpretation of DTT with Pi-, 1-, Sigma- and intensional Id-types and, additionally, finite inductive type families. This smaller model is fully (and faithfully) complete with respect to the syntax at the type hierarchy built without Id-types, as well as at the more general class of types where we allow for one strictly positive occurrence of an Id-type. Definability for the full type hierarchy with Id-types remains to be investigated. (C) 2018 Published by Elsevier Inc.
引用
收藏
页码:401 / 431
页数:31
相关论文
共 50 条
  • [1] From CSP to Game Semantics
    Abramsky, Samson
    REFLECTIONS ON THE WORK OF C A R HOARE, 2010, : 33 - 45
  • [2] DISENTANGLING PARALLELISM AND INTERFERENCE IN GAME SEMANTICS
    Castellan, Simon
    Clairambault, Pierre
    LOGICAL METHODS IN COMPUTER SCIENCE, 2024, 20 (03)
  • [3] Game Semantics for a Polymorphic Programming Language
    Laird, J.
    25TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2010), 2010, : 41 - 49
  • [4] Dynamic game semantics
    Yamada, Norihiro
    Abramsky, Samson
    MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE, 2020, 30 (08) : 892 - 951
  • [5] Game Semantics for Interface Middleweight Java']Java
    Murawski, Andrzej S.
    Tzevelekos, Nikos
    ACM SIGPLAN NOTICES, 2014, 49 (01) : 517 - 528
  • [6] Algorithmic probabilistic game semantics
    Kiefer, Stefan
    Murawski, Andrzej S.
    Ouaknine, Joel
    Wachter, Bjoern
    Worrell, James
    FORMAL METHODS IN SYSTEM DESIGN, 2013, 43 (02) : 285 - 312
  • [7] Game Semantics for Quantum Programming
    Clairambault, Pierre
    De Visme, Marc
    Winskel, Glynn
    PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL, 2019, 3 (POPL):
  • [8] Game Semantics for a Polymorphic Programming Language
    Laird, J.
    JOURNAL OF THE ACM, 2013, 60 (04)
  • [9] A game semantics for disjunctive logic programming
    Tsouanas, Thanos
    ANNALS OF PURE AND APPLIED LOGIC, 2013, 164 (11) : 1144 - 1175
  • [10] A game semantics for Grz
    Mezhirov, Ilya
    JOURNAL OF LOGIC AND COMPUTATION, 2006, 16 (05) : 663 - 669