| 作成者 |
|
|
|
|
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連情報 |
|
|
|
| 概要 |
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 gr...aphs 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 left(log^2 n+log m \right)$ time with $O left(n+m \right)$ processors on an EREW PRAM. For the FGS defining outerplanar graphs, we show that the refutation tree problem can be solved in $O left(log^2 n \right)$ time with $Oleft(n+rn)$ processors on an EREW PRAM. Here, n and m are the numbers of vertices and edges of an input graph, respectively.続きを見る
|
Mendeley出力
rifis-tr-59