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 条
  • [21] ActorGame: Game Semantics for Actors
    Wang, Yong
    Dai, Guiping
    2013 FOURTH GLOBAL CONGRESS ON INTELLIGENT SYSTEMS (GCIS), 2013, : 5 - 10
  • [22] Game Semantics and Normalization by Evaluation
    Clairambault, Pierre
    Dybjer, Peter
    FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATION STRUCTURES (FOSSACS 2015), 2015, 9034 : 56 - 70
  • [23] Game Semantics for Access Control
    Abramsky, Samson
    Jagadeesan, Radha
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2009, 249 : 135 - 156
  • [24] Operational Nominal Game Semantics
    Jaber, Guilhem
    FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATION STRUCTURES (FOSSACS 2015), 2015, 9034 : 264 - 278
  • [25] Operational Algorithmic Game Semantics
    Bunting, Benedict
    Murawski, Andrzej S.
    2023 38TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, LICS, 2023,
  • [26] A game semantics of names and pointers
    Laird, J.
    ANNALS OF PURE AND APPLIED LOGIC, 2008, 151 (2-3) : 151 - 169
  • [27] Game Semantics for Nominal Exceptions
    Murawski, Andrzej S.
    Tzevelekos, Nikos
    FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATION STRUCTURES, 2014, 8412 : 164 - 179
  • [28] Game Semantics for Vague Quantification
    Fermueller, Christian G.
    LOGICA YEARBOOK 2015, 2016, : 71 - 86
  • [29] Game Semantics in the Nominal Model
    Gabbay, Murdoch
    Ghica, Dan
    ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2012, 286 : 173 - 189
  • [30] A Game Semantics for System P
    J. Marti
    R. Pinosio
    Studia Logica, 2016, 104 : 1119 - 1144