Compositional Coinduction with Sized Types

Abstract : Proofs by induction on some inductively defined structure, e. g., finitely-branching trees, may appeal to the induction hypothesis at any point in the proof, provided the induction hypothesis is only used for immediate substructures, e. g., the subtrees of the node we are currently considering in the proof. The basic principle of structural induction can be relaxed to course-of-value induction, which allows application of the induction hypothesis also to non-immediate substructures, like any proper subtree of the current tree. If course-of-value induction is not sufficient yet, we can resort to define a well-founded relation on the considered structure and use the induction hypothesis for any substructure which is strictly smaller with regard to the constructed relation.
Type de document :
Communication dans un congrès
Ichiro Hasuo. 13th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2016, Eindhoven, Netherlands. Lecture Notes in Computer Science, LNCS-9608, pp.5-10, 2016, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-319-40370-0_2〉
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01446030
Contributeur : Hal Ifip <>
Soumis le : mercredi 25 janvier 2017 - 15:24:20
Dernière modification le : mercredi 18 octobre 2017 - 09:58:27
Document(s) archivé(s) le : mercredi 26 avril 2017 - 15:44:17

Fichier

 Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Andreas Abel. Compositional Coinduction with Sized Types. Ichiro Hasuo. 13th International Workshop on Coalgebraic Methods in Computer Science (CMCS), Apr 2016, Eindhoven, Netherlands. Lecture Notes in Computer Science, LNCS-9608, pp.5-10, 2016, Coalgebraic Methods in Computer Science. 〈10.1007/978-3-319-40370-0_2〉. 〈hal-01446030〉

Partager

Métriques

Consultations de la notice

38