On the parsing of deterministic graph languages for syntactic pattern recognition

摘要

Further results of research into parsing of graph grammars for syntactic pattern recognition are presented (Comput. Vision Graphics Image Process.47, 1–21 (1989); Pattern Recognition23, 765–774 (1990)). A defined ETPL(k) graph grammar is a subfamily of a well-known edNLC graph grammar (Janssens and Rozenberg, Inf. Sci.20, 191–216 (1980)) being a strong formalism for pattern representation. The subfamily generates a wider class of languages than the ones presented in the previous papers. An efficient parsing algorithm is constructed, its time complexity, o(n2), is evaluated, and experimental results are included.