
arXiv: 0705.4226
The characterization of second-order type isomorphisms is a purely syntactical problem that we propose to study under the enlightenment of game semantics. We study this question in the case of second-order ��$��$-calculus, which can be seen as an extension of system F to classical logic, and for which we de���ne a categorical framework: control hyperdoctrines. Our game model of ��$��$-calculus is based on polymorphic arenas (closely related to Hughes' hyperforests) which evolve during the play (following the ideas of Murawski-Ong). We show that type isomorphisms coincide with the "equality" on arenas associated with types. Finally we deduce the equational characterization of type isomorphisms from this equality. We also recover from the same model Roberto Di Cosmo's characterization of type isomorphisms for system F. This approach leads to a geometrical comprehension on the question of second order type isomorphisms, which can be easily extended to some other polymorphic calculi including additional programming features.
accepted by Annals of Pure and Applied Logic, Special Issue on Game Semantics
Second-order λμ-calculus, FOS: Computer and information sciences, Logic in computer science, control categories, Computer Science - Logic in Computer Science, Game semantics, Control categories, polymorphic arenas, Logic, Semantics in the theory of computing, second-order \(\lambda \mu \)-calculus, Types isomorphisms, game semantics, Logic in Computer Science (cs.LO), type isomorphisms, Categorical semantics of formal languages, hyperdoctrines, Applications of game theory, Combinatory logic and lambda calculus, F.3.2, Hyperdoctrines
Second-order λμ-calculus, FOS: Computer and information sciences, Logic in computer science, control categories, Computer Science - Logic in Computer Science, Game semantics, Control categories, polymorphic arenas, Logic, Semantics in the theory of computing, second-order \(\lambda \mu \)-calculus, Types isomorphisms, game semantics, Logic in Computer Science (cs.LO), type isomorphisms, Categorical semantics of formal languages, hyperdoctrines, Applications of game theory, Combinatory logic and lambda calculus, F.3.2, Hyperdoctrines
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 6 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
