Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-25004
Titel: | Terminological cycles and the ropositional μ-calculus |
VerfasserIn: | Schild, Klaus |
Sprache: | Englisch |
Erscheinungsjahr: | 1993 |
Quelle: | Kaiserslautern ; Saarbrücken : DFKI, 1993 |
Kontrollierte Schlagwörter: | Künstliche Intelligenz |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Forschungsbericht (Report zu Forschungsprojekten) |
Abstract: | We investigate terminological cycles in the terminological standard logic mathcal{ALC} with the only restriction that recursively defined concepts must occur in their definition positively. This restriction, called syntactic monotonicity, ensures the existence of least and greatest fixpoint models. It turns out that as far as syntactically monotone terminologies of mathcal{ALC} are concerned, the descriptive semantics as well as the least and greatest fixpoint semantics do not differ in the computational complexity of the corresponding subsumption relation. In fact, we prove that in each case subsumption is complete for deterministic exponential time. We then show that the expressive power of finite sets of syntactically monotone terminologies of mathcal{ALC} is the very same for the least and the greatest fixpoint semantics and, moreover, in both cases they are strictly stronger in expressive power than mathcal{ALC} augmented by regular role expressions. These results are obtained by a direct correspondence to the so-called propositional mu-calculus which allows to express least and greatest fixpoints explicitly. We propose ALC augmented by the fixpoint operators of the mu-calculus as a unifying framework for all three kinds of semantics. |
Link zu diesem Datensatz: | urn:nbn:de:bsz:291-scidok-38145 hdl:20.500.11880/25060 http://dx.doi.org/10.22028/D291-25004 |
Schriftenreihe: | Research report / Deutsches Forschungszentrum für Künstliche Intelligenz [ISSN 0946-008x] |
Band: | 93-18 |
Datum des Eintrags: | 5-Jul-2011 |
Fakultät: | SE - Sonstige Einrichtungen |
Fachrichtung: | SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
RR_93_18.pdf | 22,47 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.