@inproceedings{cccfedcef749460c85806ba649adbcfe,

title = "Graph Transformation in Constant Time",

abstract = "We present conditions under which graph transformation rules can be applied in time independent of the size of the input graph: graphs must contain a unique root label, nodes in the left-hand sides of rules must be reachable from the root, and nodes must have a bounded outdegree. We establish a constant upper bound for the time needed to construct all graphs resulting from an application of a fixed rule to an input graph. We also give an improved upper bound under the stronger condition that all edges outgoing from a node must have distinct labels. Then this result is applied to identify a class of graph reduction systems that define graph languages with a linear membership test. In a case study we prove that the (non-context-free) language of balanced binary trees with backpointers belongs to this class.",

author = "Mike Dodds and Detlef Plump",

year = "2006",

doi = "10.1007/11841883_26",

language = "English",

isbn = "3-540-38870-2",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "367--382",

editor = "A Corradini and H Ehrig and U Montanari and L Ribeiro and G Rozenberg",

booktitle = "Proceedings 3rd International Conference on Graph Transformation (ICGT 2006)",

address = "Germany",

note = "3rd International Conference on Graph Transformations ; Conference date: 17-09-2006 Through 23-09-2006",

}