Parsing of edNLC-graph grammars for scene analysis (Q1114425)

An edNLC-graph grammar, introduced by \textit{D. Janssens} and \textit{G. Rozenberg} [Inf. Sci. 20, 191-216 (1980; Zbl 0452.68073)] is a strong formalism for generating scene representations. This grammar generates directed node- and edge-labelled graphs, EDG-graphs. A method of construction of unambiguous string EDG-graph representation is briefly described. The characteristics of edNLC-graph grammar for syntactic pattern recognition allows us to construct the parsing algorithm. The deterministic top-down syntax analyser is constructed for the subfamily of an edNLC-graph grammar, called an ETL/1-graph grammar. An ETl/1-graph grammar is parallel to a finite state string grammar. The notions introduced in the paper are useful for researchers in less restricted edNLC-graph grammars, for example grammars analogical to context-free string grammars.