Grammars for Rooted Acyclic Directed Graphs and Their Parsing
Summary :
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.
- Publication
- IEICE TRANSACTIONS on transactions Vol.E71-E No.4 pp.414-421
- Publication Date
- 1988/04/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Automaton, Language and Theory of Computing
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Chun-YeLI, Toshio KAWASHIMA, Yoshinao AOKI, "Grammars for Rooted Acyclic Directed Graphs and Their Parsing" in IEICE TRANSACTIONS on transactions,
vol. E71-E, no. 4, pp. 414-421, April 1988, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e71-e_4_414/_p
Copy
@ARTICLE{e71-e_4_414,
author={Chun-YeLI, Toshio KAWASHIMA, Yoshinao AOKI, },
journal={IEICE TRANSACTIONS on transactions},
title={Grammars for Rooted Acyclic Directed Graphs and Their Parsing},
year={1988},
volume={E71-E},
number={4},
pages={414-421},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={April},}
Copy
TY - JOUR
TI - Grammars for Rooted Acyclic Directed Graphs and Their Parsing
T2 - IEICE TRANSACTIONS on transactions
SP - 414
EP - 421
AU - Chun-YeLI
AU - Toshio KAWASHIMA
AU - Yoshinao AOKI
PY - 1988
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E71-E
IS - 4
JA - IEICE TRANSACTIONS on transactions
Y1 - April 1988
AB - 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.
ER -
English
