Chapter 10: Pattern Analysis with Graph Grammars

Graph grammars are the strongest descriptive/generative formalism in the theory of formal languages [Pfaltz and Rosenfeld (1969); Montanari (1970); Pavlidis (1972a, 1980); Pfaltz (1972); Abe et al. (1973)], since one can define every kind of relation among the structure components. Therefore graph grammars have been used for the synthesis/generation of formal representations in various areas of computer science such as computer graphics and vision, programming languages and compiler design, software engineering, database design, distributed and concurrent computing etc., [Ehrig et al. (1999)] for more than half a century. On the other hand, only a few graph language parsers used as tools for the analysis/recognition of graph patterns in syntactic pattern recognition have been presented over the course of this time. It results from the intractability of the problem of parsing for graph grammars. Graph-based syntactic pattern recognition models are presented in this chapter…