Axioms and Decidability for Type Isomorphism in the Presence of Sums

Danko Ilik 1
1 PARSIFAL - Proof search and reasoning with logic specifications
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : We consider the problem of characterizing isomorphisms of types, or, equivalently, constructive cardinality of sets, in the simultaneous presence of disjoint unions, Cartesian products, and exponentials. Mostly relying on results about polynomials with exponentiation that have not been used in our context, we derive: that the usual finite axiomatization known as High-School Identities (HSI) is complete for a significant subclass of types; that it is decidable for that subclass when two types are isomorphic; that, for the whole of the set of types, a recursive extension of the axioms of HSI exists that is complete; and that, for the whole of the set of types, the question as to whether two types are isomorphic is decidable when base types are to be interpreted as finite sets. We also point out certain related open problems.
Type de document :
Communication dans un congrès
Henzinger, Thomas and Miller, Dale. CSL-LICS '14 Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Jul 2014, Vienna, Austria. ACM, 2014, <10.1145/2603088.2603115>
Liste complète des métadonnées

https://hal.inria.fr/hal-00991147
Contributeur : Danko Ilik <>
Soumis le : mercredi 14 mai 2014 - 19:03:03
Dernière modification le : jeudi 9 février 2017 - 15:09:41
Document(s) archivé(s) le : jeudi 14 août 2014 - 12:06:30

Fichiers

sumaxioms.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Danko Ilik. Axioms and Decidability for Type Isomorphism in the Presence of Sums. Henzinger, Thomas and Miller, Dale. CSL-LICS '14 Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Jul 2014, Vienna, Austria. ACM, 2014, <10.1145/2603088.2603115>. <hal-00991147>

Partager

Métriques

Consultations de
la notice

397

Téléchargements du document

132