My current favorite paper of the month: "An efficient implementation of graph grammars based on the RETE matching algorithm" by H. Bunke, T. Glauser, T. Tran
http://dx.doi.org/10.1007/BFb0017389
Abstract: This paper is concerned with the efficient determination of the set of productions of a graph grammar that are applicable in one rewriting step. We propose a new algorithm that is a generalization of a similar algorithm originally developed for forward chaining production systems. The time complexity of the proposed method is not better than that of a naive solution, in the worst case. In the best case, however, a significant speedup can be achieved. Some experiments supporting the results of a theoretical complexity analysis are described.
Abstract: This paper is concerned with the efficient determination of the set of productions of a graph grammar that are applicable in one rewriting step. We propose a new algorithm that is a generalization of a similar algorithm originally developed for forward chaining production systems. The time complexity of the proposed method is not better than that of a naive solution, in the worst case. In the best case, however, a significant speedup can be achieved. Some experiments supporting the results of a theoretical complexity analysis are described.