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é

We study the computational model of polygraphs. For that, we consider polygraphic programs, a subclass of these objects, as a formal description of first-order functional programs. We explain their semantics and prove that they form a Turing-complete computational model. Their algebraic structure is used by analysis tools, called polygraphic interpretations, for complexity analysis. In particular, we delineate a subclass of polygraphic programs that compute exactly the functions that are Turing-computable in polynomial time.
Fichier principal
Vignette du fichier
polypoly.pdf (575.6 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 2

Citer

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

Partager

Gmail Facebook X LinkedIn More