Observation of implicit complexity by non confluence

Guillaume Bonfante 1
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : We propose to consider non confluence with respect to implicit complexity. We come back to some well known classes of first-order functional program, for which we have a characterization of their intentional properties, namely the class of cons-free programs, the class of programs with an inter- pretation, and the class of programs with a quasi-interpretation together with a termination proof by the product path ordering. They all correspond to PTIME. We prove that adding non confluence to the rules leads to respectively PTIME, NPTIME and PSPACE. Our thesis is that the separation of the classes is actually a witness of the intentional properties of the initial classes of programs.
Type de document :
Communication dans un congrès
International Workshop on Developments in Implicit Computational complExity - DICE 2010, Mar 2010, Paphos, Cyprus. 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00535539
Contributeur : Guillaume Bonfante <>
Soumis le : jeudi 11 novembre 2010 - 14:19:22
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : vendredi 26 octobre 2012 - 15:26:49

Fichier

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

Identifiants

  • HAL Id : inria-00535539, version 1

Collections

Citation

Guillaume Bonfante. Observation of implicit complexity by non confluence. International Workshop on Developments in Implicit Computational complExity - DICE 2010, Mar 2010, Paphos, Cyprus. 2010. 〈inria-00535539〉

Partager

Métriques

Consultations de la notice

263

Téléchargements de fichiers

101