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 条
  • [31] Game Semantics for Quantum Stores
    Delbecque, Yannick
    Panagaden, Prakash
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2008, 218 (153-170) : 153 - 170
  • [32] An argument game for stable semantics
    Caminada, Martin
    Wu, Yining
    LOGIC JOURNAL OF THE IGPL, 2009, 17 (01) : 77 - 90
  • [33] Game Semantics for Quantum Data
    Delbecquea, Yannick
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2011, 270 (01) : 41 - 57
  • [34] Refinement-Based Game Semantics for Certified Abstraction Layers
    Koenig, Jeremie
    Shao, Zhong
    PROCEEDINGS OF THE 35TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2020), 2020, : 633 - 647
  • [35] Game Semantics for Modal Logic with Counting
    Fu, Xiaoxuan
    Zhao, Zhiguang
    ARTIFICIAL INTELLIGENCE LOGIC AND APPLICATIONS, AILA 2024, 2025, 2248 : 3 - 16
  • [36] An Algebraic Account of References in Game Semantics
    Mellies, Paul-Andre
    Tabareau, Nicolas
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2009, 249 : 377 - 405
  • [37] Abstract machines for game semantics, revisited
    Fredriksson, Olle
    Ghica, Dan R.
    2013 28TH ANNUAL IEEE/ACM SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2013, : 560 - 569
  • [38] A Quantum Game Semantics for the Measurement Calculus
    Delbecque, Yannick
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2008, 210 (0C) : 33 - 48
  • [39] A type assignment system for game semantics
    Di Gianantonio, Pietro
    Honsell, Furio
    Lenisa, Marina
    THEORETICAL COMPUTER SCIENCE, 2008, 398 (1-3) : 150 - 169
  • [40] The concurrent game semantics of Probabilistic PCF
    Castellan, Simon
    Clairambault, Pierre
    Paquet, Hugo
    Winskel, Glynn
    LICS'18: PROCEEDINGS OF THE 33RD ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, 2018, : 215 - 224