Please use this identifier to cite or link to this item:
doi:10.22028/D291-25004
Title: | Terminological cycles and the ropositional μ-calculus |
Author(s): | Schild, Klaus |
Language: | English |
Year of Publication: | 1993 |
OPUS Source: | Kaiserslautern ; Saarbrücken : DFKI, 1993 |
SWD key words: | Künstliche Intelligenz |
DDC notations: | 004 Computer science, internet |
Publikation type: | Report |
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 to this record: | urn:nbn:de:bsz:291-scidok-38145 hdl:20.500.11880/25060 http://dx.doi.org/10.22028/D291-25004 |
Series name: | Research report / Deutsches Forschungszentrum für Künstliche Intelligenz [ISSN 0946-008x] |
Series volume: | 93-18 |
Date of registration: | 5-Jul-2011 |
Faculty: | SE - Sonstige Einrichtungen |
Department: | SE - DFKI Deutsches Forschungszentrum für Künstliche Intelligenz |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
RR_93_18.pdf | 22,47 MB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.