Tractable and Decidable Fragments of Conceptual Graphs

Franz BaaderFranz Baader, R. MolitorR. Molitor, Stephan TobiesStephan Tobies

Datei:BaaderMolitorTobies-ICCS-1999.ps.gz

Download

Franz Baader, R. Molitor, Stephan 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},
}