LATPub165: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
||
| (2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 1: | Zeile 1: | ||
{{Publikation Erster Autor | {{Publikation Erster Autor | ||
|ErsterAutorVorname= | |ErsterAutorVorname=Franz | ||
|ErsterAutorNachname=Baader | |ErsterAutorNachname=Baader | ||
|FurtherAuthors=R. Molitor; | |FurtherAuthors=R. Molitor; Stephan Tobies | ||
}} | }} | ||
{{Inproceedings | {{Inproceedings | ||
| Zeile 10: | Zeile 10: | ||
|Month= | |Month= | ||
|Booktitle=Proceedings of the Seventh International Conference on Conceptual Structures (ICCS'99) | |Booktitle=Proceedings of the Seventh International Conference on Conceptual Structures (ICCS'99) | ||
|Editor=W. | |Editor=W. Cyre and W. Tepfenhart | ||
|Note= | |Note= | ||
|Organization= | |Organization= | ||
|Pages=480 | |Pages=480-493 | ||
|Publisher=Springer | |Publisher=Springer | ||
|Series=Lecture Notes in Computer Science | |Series=Lecture Notes in Computer Science | ||
| Zeile 20: | Zeile 20: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract= | |Abstract= 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.'' | ||
|ISBN= | |ISBN= | ||
|ISSN= | |ISSN= | ||
| Zeile 53: | Zeile 40: | ||
year = {1999}, | year = {1999}, | ||
} | } | ||
}} | }} | ||
Aktuelle Version vom 25. März 2015, 16:34 Uhr
Tractable and Decidable Fragments of Conceptual Graphs
Franz BaaderFranz Baader, R. MolitorR. Molitor, Stephan TobiesStephan Tobies
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
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
- 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
@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},
}
