| Creator |
|
|
|
|
|
| Language |
|
| Publisher |
|
|
|
| Date |
|
|
|
| Source Title |
|
| Vol |
|
| Issue |
|
| First Page |
|
| Last Page |
|
| Publication Type |
|
| Access Rights |
|
| Crossref DOI |
|
| Related DOI |
|
| Related DOI |
|
|
|
|
|
| Related URI |
|
|
|
|
|
| Relation |
|
|
|
|
|
|
|
| Abstract |
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.show more
|
Export Mendeley
