IEICE TRANSACTIONS on Information
Parallel Algorithms for Refutation Tree Problem on Formal Graph Systems
Summary :
We define a new framework for rewriting graphs, called a formal graph system (FGS), which is a logic program having hypergraphs instead of terms in first-order logic. We first prove that a class of graphs is generated by a hyperedge replacement grammar if and only if it is defined by an FGS of a special form called a regular FGS. In the same way as logic programs, we can define a refutation tree for an FGS. The classes of TTSP graphs and outerplanar graphs are definable by regular FGSs. Then, we consider the problem of constructing a refutation tree of a graph for these FGSs. For the FGS defining TTSP graphs, we present a refutation tree algorithm of O(log2n
- Publication
- IEICE TRANSACTIONS on Information Vol.E78-D No.2 pp.99-112
- Publication Date
- 1995/02/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Algorithm and Computational Complexity
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
Tomoyuki UCHIDA, Takayoshi SHOUDAI, Satoru MIYANO, "Parallel Algorithms for Refutation Tree Problem on Formal Graph Systems" in IEICE TRANSACTIONS on Information,
vol. E78-D, no. 2, pp. 99-112, February 1995, doi: .
Abstract: We define a new framework for rewriting graphs, called a formal graph system (FGS), which is a logic program having hypergraphs instead of terms in first-order logic. We first prove that a class of graphs is generated by a hyperedge replacement grammar if and only if it is defined by an FGS of a special form called a regular FGS. In the same way as logic programs, we can define a refutation tree for an FGS. The classes of TTSP graphs and outerplanar graphs are definable by regular FGSs. Then, we consider the problem of constructing a refutation tree of a graph for these FGSs. For the FGS defining TTSP graphs, we present a refutation tree algorithm of O(log2n
URL: https://global.ieice.org/en_transactions/information/10.1587/e78-d_2_99/_p
Copy
@ARTICLE{e78-d_2_99,
author={Tomoyuki UCHIDA, Takayoshi SHOUDAI, Satoru MIYANO, },
journal={IEICE TRANSACTIONS on Information},
title={Parallel Algorithms for Refutation Tree Problem on Formal Graph Systems},
year={1995},
volume={E78-D},
number={2},
pages={99-112},
abstract={We define a new framework for rewriting graphs, called a formal graph system (FGS), which is a logic program having hypergraphs instead of terms in first-order logic. We first prove that a class of graphs is generated by a hyperedge replacement grammar if and only if it is defined by an FGS of a special form called a regular FGS. In the same way as logic programs, we can define a refutation tree for an FGS. The classes of TTSP graphs and outerplanar graphs are definable by regular FGSs. Then, we consider the problem of constructing a refutation tree of a graph for these FGSs. For the FGS defining TTSP graphs, we present a refutation tree algorithm of O(log2n
keywords={},
doi={},
ISSN={},
month={February},}
Copy
TY - JOUR
TI - Parallel Algorithms for Refutation Tree Problem on Formal Graph Systems
T2 - IEICE TRANSACTIONS on Information
SP - 99
EP - 112
AU - Tomoyuki UCHIDA
AU - Takayoshi SHOUDAI
AU - Satoru MIYANO
PY - 1995
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E78-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 1995
AB - We define a new framework for rewriting graphs, called a formal graph system (FGS), which is a logic program having hypergraphs instead of terms in first-order logic. We first prove that a class of graphs is generated by a hyperedge replacement grammar if and only if it is defined by an FGS of a special form called a regular FGS. In the same way as logic programs, we can define a refutation tree for an FGS. The classes of TTSP graphs and outerplanar graphs are definable by regular FGSs. Then, we consider the problem of constructing a refutation tree of a graph for these FGSs. For the FGS defining TTSP graphs, we present a refutation tree algorithm of O(log2n
ER -
English
