1-1hit |
Chun-YeLI Toshio KAWASHIMA Yoshinao AOKI
In this paper, we introduce the concepts of multi-node and mono-node to expand the expansive graph grammar given by Shi and Fu to a larger family, the family that contains all rooted acyclic directed graphs. Shi and Fu's approach deals with rooted acyclic digraphs containing only mono-nodes. The ways of numbering and representing rooted acyclic directed graphs are modified and grammars for such graphs are given so that directed graphs containing even multi-nodes can be treated. Parsing algorithms are also given which are described with State-Space representation. Our algorithms are as efficient as those of Ref.(6). We have removed a constraint that the basis graph must be a tree from the expansive graph grammars of Ref.(6) without increasing the space or time complexity of numbering, rewriting and parsing.