Graph Transformation in Constant Time

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish
Title of host publicationProceedings 3rd International Conference on Graph Transformation (ICGT 2006)
EditorsA Corradini, H Ehrig, U Montanari, L Ribeiro, G Rozenberg
Place of PublicationBerlin
Number of pages16
ISBN (Print)3-540-38870-2
Publication statusPublished - 2006
Event3rd International Conference on Graph Transformations - Natal
Duration: 17 Sept 200623 Sept 2006

Publication series

NameLecture Notes in Computer Science


Conference3rd International Conference on Graph Transformations

Cite this