[DL] Campactness

[Carsten Lutz]

On Fri, 19 Jan 2007, Marcio Moretto Ribeiro wrote:
>
> I would like to ask about the compactness of the description logics. Which
> dls are compact?  Or what characteristic makes a dl compact? Is every dl
> compact?
> I have searched the literature and the web, but I haven't found any work
> mentioning the compatness of the description logics.

All DLs which are fragments of first-order logic inherit compactness, 
which includes e.g. EL, ALC, SHIQ, and OWL-DL. However, it is not true 
that all DLs are compact. Take for example ALC_reg, i.e., ALC extended
with the role operators union, composition, and reflexive-transitive
closure. This DL is a notational variant of PDL (Propositional Dynamic
Logic), and the latter is well-known to be not compact (c.f. for example
the monograph on PDL by HarelKozenTiuryn).

greetings,
 		Carsten

--
*      Carsten Lutz, Institut f"ur Theoretische Informatik, TU Dresden       *
*     Office phone:++49 351 46339171   mailto:lutz at tcs.inf.tu-dresden.de     *