Eingang zum Volltext in SciDok


Report (Bericht) zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-38145

Terminological cycles and the ropositional μ-calculus

Schild, Klaus

Quelle: (1993) Kaiserslautern ; Saarbrücken : DFKI, 1993
Dokument 1.pdf (22.469 KB)

Bookmark bei Connotea Bookmark bei
SWD-Schlagwörter: Künstliche Intelligenz
Institut: DFKI Deutsches Forschungszentrum für Künstliche Intelligenz
DDC-Sachgruppe: Informatik
Dokumentart: Report (Bericht)
Schriftenreihe: Research report / Deutsches Forschungszentrum für Künstliche Intelligenz [ISSN 0946-008x]
Bandnummer: 93-18
Sprache: Englisch
Erstellungsjahr: 1993
Publikationsdatum: 05.07.2011
Kurzfassung auf Englisch: 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.
Lizenz: Standard-Veröffentlichungsvertrag

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English