Algorithms with Polynomial Interpretation Termination Proof

Abstract : We study the effect of polynomial interpretation termination proofs of deterministic (resp. non-deterministic) algorithms defined by confluent (resp. non-confluent) rewrite systems over data structures which include strings, lists and trees, and we classify them according to the interpretations of the constructors. This leads to the definition of six function classes which turn out to be exactly the deterministic (resp. non-deterministic) polynomial time, linear exponential time and linear doubly exponential time computable functions when the class is based on confluent (resp. non-confluent) rewrite systems. We also obtain a characterisation of the linear space computable functions. Finally, we demonstrate that functions with exponential interpretation termination proofs are super-elementary.
Type de document :
Article dans une revue
Journal of Functional Programming, Cambridge University Press (CUP), 2001, 11 (1), pp.33-53
Liste complète des métadonnées

https://hal.inria.fr/inria-00100819
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:51:34
Dernière modification le : jeudi 11 janvier 2018 - 06:20:12

Identifiants

  • HAL Id : inria-00100819, version 1

Collections

Citation

Guillaume Bonfante, Adam Cichon, Jean-Yves Marion, Helene Touzet. Algorithms with Polynomial Interpretation Termination Proof. Journal of Functional Programming, Cambridge University Press (CUP), 2001, 11 (1), pp.33-53. 〈inria-00100819〉

Partager

Métriques

Consultations de la notice

156