Polygraphic programs and polynomial-time functions

Guillaume Bonfante 1 Yves Guiraud 2
1 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
2 PROTHEO - Constraints, automatic deduction and software properties proofs
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : 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.
Type de document :
Article dans une revue
Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2009, 5 (2:14), pp.1-37. 〈10.2168/LMCS-5(2:14)2009〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00122932
Contributeur : Yves Guiraud <>
Soumis le : mardi 12 mai 2009 - 11:52:30
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : samedi 26 novembre 2016 - 08:33:44

Fichier

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

Identifiants

Collections

Citation

Guillaume Bonfante, Yves Guiraud. Polygraphic programs and polynomial-time functions. Logical Methods in Computer Science, Logical Methods in Computer Science Association, 2009, 5 (2:14), pp.1-37. 〈10.2168/LMCS-5(2:14)2009〉. 〈inria-00122932v3〉

Partager

Métriques

Consultations de la notice

399

Téléchargements de fichiers

305