The search functionality is under construction.
The search functionality is under construction.

Author Search Result

[Author] Chun-YeLI(1hit)

1-1hit
  • Grammars for Rooted Acyclic Directed Graphs and Their Parsing

    Chun-YeLI  Toshio KAWASHIMA  Yoshinao AOKI  

     
    PAPER-Automaton, Language and Theory of Computing

      Vol:
    E71-E No:4
      Page(s):
    414-421

    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.