@InProceedings{Dodds-Plump06gratraconstant,
author = "Mike Dodds and Detlef Plump",
title = "Graph Transformation in Constant Time",
booktitle = "Proc.\ International Conference on Graph Transformation
({ICGT} 2006)",
series = "Lecture Notes in Computer Science",
publisher = "Springer-Verlag",
year = "2006",
volume = "4178/2006",
pages = "367--382",
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."
}