@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",
}