Course of value distinguishes the intentionality of programming languages

Guillaume Bonfante 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : In this contribution, we propose to study the transformation of first order programs by course of value recursion. Our motivation is to show that this transformation provides a separation criterion for the intentionality of sets of programs. As an illustration, we consider two variants of the multiset path ordering, for the first, terms in recursive calls are compared with respect to the subterm property, for the second with respect to embedding. Under a quasi-interpretation, both characterize Ptime, the latter characterization being a new result. Once applied the transformation, we get respec- tively Ptime and Pspace thus proving that the latter set of programs contains more algorithms.
Type de document :
Communication dans un congrès
2nd International Symposium on Information and Communication Technology - SoICT 2011, Oct 2011, Hanoi, Vietnam. 2011
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00642731
Contributeur : Guillaume Bonfante <>
Soumis le : vendredi 18 novembre 2011 - 16:05:26
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : lundi 5 décembre 2016 - 06:21:40

Fichier

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

Identifiants

  • HAL Id : hal-00642731, version 1

Collections

Citation

Guillaume Bonfante. Course of value distinguishes the intentionality of programming languages. 2nd International Symposium on Information and Communication Technology - SoICT 2011, Oct 2011, Hanoi, Vietnam. 2011. 〈hal-00642731〉

Partager

Métriques

Consultations de la notice

243

Téléchargements de fichiers

100