Polygraphic programs and polynomial-time functions - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Logical Methods in Computer Science Année : 2007

Polygraphic programs and polynomial-time functions

Résumé

This study presents polygraphic programs as an algebraic and graphical description of first-order functional programs. We prove that they form a Turing-complete computational model. Using analysis tools called polygraphic interpretations, we delineate a subclass of these objects and study their computational properties: these polygraphic programs compute exactly polynomial-time functions.
Fichier principal
Vignette du fichier
poly06.pdf (294.9 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00122932 , version 1 (05-01-2007)
inria-00122932 , version 2 (13-11-2007)
inria-00122932 , version 3 (12-05-2009)

Identifiants

  • HAL Id : inria-00122932 , version 1

Citer

Guillaume Bonfante, Yves Guiraud. Polygraphic programs and polynomial-time functions. Logical Methods in Computer Science, 2007, (under revision). ⟨inria-00122932v1⟩
165 Consultations
327 Téléchargements

Partager

Gmail Facebook X LinkedIn More