Evolving graph-structures and their implicit computational complexity

Daniel Leivant 1 Jean-Yves Marion 2, *
* Auteur correspondant
1 Department of computer science
Computer Science Departement [Indiana]
2 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : Dynamic data-structures are ubiquitous in programming, and they use extensively underlying directed multi-graph structures, such as labeled trees, DAGs, and objects. This paper adapts well-established static analysis methods, namely data ramification and language-based information flow security, to programs over such graph structures. Our programs support the creation, deletion, and updates of both vertices and edges, and are related to pointer machines. The main result states that a function over graph-structures is computable in polynomial time iff it is computed by a terminating program whose graph manipulation is ramified, provided all edges that are both created and read in a loop have the same label.
Type de document :
Communication dans un congrès
ICALP, Jul 2013, RIGA, Latvia. SPRINGER, 7966, pp.349-360, 2013, LNCS
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00939484
Contributeur : Jean-Yves Marion <>
Soumis le : jeudi 30 janvier 2014 - 19:01:46
Dernière modification le : jeudi 11 janvier 2018 - 06:21:25
Document(s) archivé(s) le : dimanche 9 avril 2017 - 03:46:18

Fichier

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

Identifiants

  • HAL Id : hal-00939484, version 1

Collections

Citation

Daniel Leivant, Jean-Yves Marion. Evolving graph-structures and their implicit computational complexity. ICALP, Jul 2013, RIGA, Latvia. SPRINGER, 7966, pp.349-360, 2013, LNCS. 〈hal-00939484〉

Partager

Métriques

Consultations de la notice

255

Téléchargements de fichiers

152