Regular Description of Context-free Graph Languages

摘要

A set of (labeled) graphs can be defined by a regular tree language and one regular string language for each possible edge label, as follows. For each treetfrom the regular tree language the graph gr(t) has the same nodes ast(with the same labels), and there is an edge with labelαfrom nodexto nodeyif the string of labels of the nodes on the shortest path fromxtoyintbelongs to the regular string language forα. Slightly generalizing this definition scheme, we allow gr(t) to have only those nodes oftthat have certain labels, and we allow a relabeling of these nodes. It is shown that in this way exactly the class of C-edNCE graph languages (generated by C-edNCE graph grammars) is obtained, one of the largest known classes of context-free graph languages.