Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25004
Titel: Terminological cycles and the ropositional μ-calculus
Verfasser: Schild, Klaus
Sprache: Englisch
Erscheinungsjahr: 1993
Quelle: Kaiserslautern ; Saarbrücken : DFKI, 1993
SWD-Schlagwörter: Künstliche Intelligenz
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: 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
SciDok-Publikation: 5-Jul-2011
Fakultät: Sonstige Einrichtungen
Fachrichtung: SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz
Fakultät / Institution:SE - Sonstige Einrichtungen

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
RR_93_18.pdf22,47 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.