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 if 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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
Bellantoni, S., Cook, S.A.: A new recursion-theoretic characterization of the poly-time functions. Computational Complexity 2, 97–110 (1992)
Gurevich, Y.: Sequential abstract state machines capture sequential algorithms. ACM Transactions on Computational Logic 1(1), 77–111 (2000)
Hartmann, L., Jones, N.D., Simonsen, J.G., Vrist, S.B.: Programming in biomolecular computation: Programs, self-interpretation and visualisation. Sci. Ann. Comp. Sci. 21(1), 73–106 (2011)
Hofmann, M., Schöpp, U.: Pure pointer programs with iteration. ACM Trans. Comput. Log. 11(4) (2010)
Jones, N.D.: Logspace and ptime characterized by programming languages. Theor. Comput. Sci. 228(1-2), 151–174 (1999)
Kolmogorov, A.N., Uspensky, V.: On the definition of an algorithm. Uspekhi Mat. Naut. 13(4) (1958)
Leivant, D.: Predicative recurrence and computational complexity I: Word recurrence and poly-time. In: Feasible Mathematics II. Birkhauser-Boston (1994)
Marion, J.-Y.: A type system for complexity flow analysis. In: LICS (2011)
Sabelfeld, A., Sands, D.: Declassification: dimensions and principles. J. Comput. Secur. 17, 517–548 (2009)
Schönhage, A.: Storage modification machines. SIAM J. Comp. 9(3), 490–508 (1980)
Tarjan, R.E.: Reference machines require non-linear time to maintain disjoint sets. In: STOC 1977, pp. 18–29. ACM (1977)
Volpano, D., Irvine, C., Smith, G.: A sound type system for secure flow analysis. Journal of Computer Security 4(2/3), 167–188 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Leivant, D., Marion, JY. (2013). Evolving Graph-Structures and Their Implicit Computational Complexity. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds) Automata, Languages, and Programming. ICALP 2013. Lecture Notes in Computer Science, vol 7966. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39212-2_32
Download citation
DOI: https://doi.org/10.1007/978-3-642-39212-2_32
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39211-5
Online ISBN: 978-3-642-39212-2
eBook Packages: Computer ScienceComputer Science (R0)