Semantisches Browsen
Aus International Center for Computational Logic
This paper is concerned with decidability … 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.''nsformed into trees by ``cutting cycles.'' +
@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},
}
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},
}
Baader +
Franz +
Franz Baader, R. Molitor, Stephan Tobies&l … Franz Baader, R. Molitor, Stephan Tobies<br/> '''[[LATPub165|<b>Tractable and Decidable Fragments of Conceptual Graphs</b>]]''' <br/>__NOTOC__In W. Cyre and W. Tepfenhart, eds., <i>Proceedings of the Seventh International Conference on Conceptual Structures (ICCS'99)</i>, Lecture Notes in Computer Science, 480-493, 1999. Springer<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[LATPub165|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex; "></span> [[Media:BaaderMolitorTobies-ICCS-1999.ps.gz|Download]]BaaderMolitorTobies-ICCS-1999.ps.gz|Download]] +
Franz Baader, R. Molitor, Stephan Tobies&l … Franz Baader, R. Molitor, Stephan Tobies<br/> '''[[LATPub165/en|<b>Tractable and Decidable Fragments of Conceptual Graphs</b>]]''' <br/>__NOTOC__In W. Cyre and W. Tepfenhart, eds., <i>Proceedings of the Seventh International Conference on Conceptual Structures (ICCS'99)</i>, Lecture Notes in Computer Science, 480-493, 1999. Springer<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[LATPub165|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex;" ></span> [[Media:BaaderMolitorTobies-ICCS-1999.ps.gz|Download]]BaaderMolitorTobies-ICCS-1999.ps.gz|Download]] +
Anzeigetitel„Anzeigetitel <span style="font-size:small;">(Display title of)</span>“ ist ein softwareseitig fest definiertes Attribut, das einen eindeutigen Anzeigetitel zu einem Objekt speichert und ihm zuweist. Es wird von <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a> zur Verfügung gestellt.
Tractable and Decidable Fragments of Conceptual Graphs +
Zuletzt geändert„Zuletzt geändert <span style="font-size:small;">(Modification date)</span>“ ist ein softwareseitig fest definiertes Attribut, das das Datum der letzten Änderung einer Seite speichert. Es wird von <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a> zur Verfügung gestellt.
25. März 2015, 14:34:03 +
Hat Abfrage„Hat Abfrage <span style="font-size:small;">(Has query)</span>“ ist ein softwareseitig fest definiertes Attribut, das die Metainformationen einer Abfrage als <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Subobject">Subobjekt</a> speichert. Es wird von <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a> zur Verfügung gestellt.
Tractable and Decidable Fragments of Conceptual Graphs +, Tractable and Decidable Fragments of Conceptual Graphs +, Tractable and Decidable Fragments of Conceptual Graphs +, Tractable and Decidable Fragments of Conceptual Graphs +, Tractable and Decidable Fragments of Conceptual Graphs +, Tractable and Decidable Fragments of Conceptual Graphs + und Tractable and Decidable Fragments of Conceptual Graphs +
