Evolving graph-structures and their implicit computational complexity - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

Evolving graph-structures and their implicit computational complexity

Résumé

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

Dates et versions

hal-00939484 , version 1 (30-01-2014)

Identifiants

  • HAL Id : hal-00939484 , version 1

Citer

Daniel Leivant, Jean-Yves Marion. Evolving graph-structures and their implicit computational complexity. ICALP, Jul 2013, RIGA, Latvia. pp.349-360. ⟨hal-00939484⟩
139 Consultations
207 Téléchargements

Partager

Gmail Facebook X LinkedIn More