Skip to Main content Skip to Navigation
Conference papers

Evolving graph-structures and their implicit computational complexity

Daniel Leivant 1 Jean-Yves Marion 2, *
* Corresponding author
1 Department of computer science
Computer Science Departement [Indiana]
2 CARTE - Theoretical adverse computations, and safety
LORIA - FM - Department of Formal Methods , Inria Nancy - Grand Est
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Jean-Yves Marion Connect in order to contact the contributor
Submitted on : Thursday, January 30, 2014 - 7:01:46 PM
Last modification on : Saturday, October 16, 2021 - 11:26:05 AM
Long-term archiving on: : Sunday, April 9, 2017 - 3:46:18 AM


Files produced by the author(s)


  • HAL Id : hal-00939484, version 1



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



Record views


Files downloads