As a guest user you are not logged in or recognized by your IP address. You have
access to the Front Matter, Abstracts, Author Index, Subject Index and the full
text of Open Access publications.
We investigate the expressive power and computational complexity of [Escr ][Lscr ]ν, the extension of the lightweight description logic [Escr ][Lscr ] with concept constructors for greatest fixpoints. It is shown that [Escr ][Lscr ]ν has the same expressive power as [Escr ][Lscr ] extended with simulation quantifiers and that it can be characterized as a largest fragment of monadic second-order logic that is preserved under simulations and has finite minimal models. As in basic [Escr ][Lscr ], all standard reasoning problems for general TBoxes can be solved in polynomial time. [Escr ][Lscr ]ν has a range of very desirable properties that [Escr ][Lscr ] itself is lacking. Firstly, least common subsumers w.r.t. general TBoxes as well as most specific concepts always exist and can be computed in polynomial time. Secondly, [Escr ][Lscr ]ν shares with [Escr ][Lscr ] the Craig interpolation property and the Beth definability property, but in contrast to [Escr ][Lscr ] allows the computation of interpolants and explicit concept definitions in polynomial time.
This website uses cookies
We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the privacy policy of IOS Press.
This website uses cookies
We use cookies to provide you with the best possible experience. They also allow us to analyze user behavior in order to constantly improve the website for you. Info about the privacy policy of IOS Press.