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
|