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.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-00642731
Contributor : Guillaume Bonfante <>
Submitted on : Friday, November 18, 2011 - 4:05:26 PM
Last modification on : Tuesday, December 18, 2018 - 4:48:02 PM
Document(s) archivé(s) le : Monday, December 5, 2016 - 6:21:40 AM

File

89bonfante.pdf
Files produced by the author(s)

Identifiers

  • 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. ⟨hal-00642731⟩

Share

Metrics

Record views

276

Files downloads

120