Tractable and Decidable Fragments of Conceptual Graphs

F. BaaderF. Baader, R. MolitorR. Molitor, S. TobiesS. Tobies

Datei:BaaderMolitorTobies-ICCS-1999.ps.gz

Download

F. Baader, R. Molitor, S. Tobies
Tractable and Decidable Fragments of Conceptual Graphs
In W. {Cyre} and W. {Tepfenhart}, eds., Proceedings of the Seventh International Conference on Conceptual Structures (ICCS'99), Lecture Notes in Computer Science, 480--493, 1999. Springer

Details
Bibtex

KurzfassungAbstract
This paper is concerned with decidability and tractability of reasoning in

 conceptual graphs (CGs). It is well-known that problems like validity and
 subsumption of general CGs are undecidable, whereas subsumption is NP-complete
 for simple conceptual graphs (SGs) and tractable for the fragment of SGs that
 are trees.  On the one hand, we will employ results on decidable fragments of
 first-order logic to identify a natural and expressive fragment of CGs for
 which validity and subsumption is decidable in deterministic exponential time.
 On the other hand, we will extend existing work on the connection between SGs
 and description logics (DLs) by identifying a DL that corresponds to the class
 of SGs that are trees. This yields a previously unknown tractability result
 for the DL in question. As a by-product, we will extend the tractability
 results for trees to SGs that can be transformed into trees by ``cutting

cycles.

Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@inproceedings{ BaaderMolitor+-ICCS-1999,
  author = {F. {Baader} and R. {Molitor} and S. {Tobies}},
  booktitle = {Proceedings of the Seventh International Conference on Conceptual Structures (ICCS'99)},
  editor = {W. {Cyre} and W. {Tepfenhart}},
  number = {1640},
  pages = {480--493},
  publisher = {Springer Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Tractable and Decidable Fragments of Conceptual Graphs},
  year = {1999},
}