Observation of implicit complexity by non confluence - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

Observation of implicit complexity by non confluence

Résumé

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.
Fichier principal
Vignette du fichier
dice.pdf (153.39 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00535539 , version 1 (11-11-2010)

Identifiants

  • HAL Id : inria-00535539 , version 1

Citer

Guillaume Bonfante. Observation of implicit complexity by non confluence. International Workshop on Developments in Implicit Computational complExity - DICE 2010, Mar 2010, Paphos, Cyprus. ⟨inria-00535539⟩
110 Consultations
90 Téléchargements

Partager

Gmail Facebook X LinkedIn More