| 作成者 |
|
|
|
|
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
|
|
| 収録物名 |
|
| 巻 |
|
| 号 |
|
| 開始ページ |
|
| 終了ページ |
|
| 出版タイプ |
|
| アクセス権 |
|
| Crossref DOI |
|
| 関連DOI |
|
| 関連DOI |
|
|
|
|
|
| 関連URI |
|
|
|
|
|
| 関連情報 |
|
|
|
|
|
|
|
| 概要 |
The refutation tree problem for a formal graph system (FGS) is to compute a refutation tree which represents the logical structure of a graph generated by the FGS. We present three subclasses of FGSs:... simple FGSs, size-bounded simple FGSs, and bounded simple FGSs. We give a polynomial-time algorithm solving the refutation tree problem for simple FGSs. For sizebounded simple FGSs generating undirected trees of constantly bounded valence, we show that a refutation tree of a graph definable by the FGS can be computed in NC^2. Moreover, we indicate that the refutation tree problem for bounded simple FGSs is in NC^2.続きを見る
|
Mendeley出力
