Deciding equivalence with sums and the empty type
Author(s) -
Gabriel Scherer
Publication year - 2017
Publication title -
acm sigplan notices
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.31
H-Index - 99
eISSN - 1558-1160
pISSN - 0362-1340
DOI - 10.1145/3093333.3009901
Subject(s) - decidability , equivalence (formal languages) , mathematics , logical equivalence , type (biology) , simple (philosophy) , pure mathematics , type theory , discrete mathematics , ecology , philosophy , epistemology , biology
The logical technique of focusing can be applied to the λ-calculus; in a simple type system with atomic types and negative type formers (functions, products, the unit type), its normal forms coincide with βη-normal forms. Introducing a saturation phase gives a notion of quasi-normal forms in presence of positive types (sum types and the empty type). This rich structure let us prove the decidability of βη-equivalence in presence of the empty type, the fact that it coincides with contextual equivalence, and with set-theoretic equality in all finite models.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom