The ALC Description Logic

The Attributive Language (AL) family of description logics allows atomic negation, concept intersection, universal restrictions, and limited existential quantification. A core AL-based description logic is the Attributive (Concept) Language with Complements (ALC), in which, unlike AL, the complement of any concept is allowed, not only the complement of atomic concepts. From the permissible constructors point of view, ALC would be equivalent to ALUE, although the latter name is not used.

ALC concept expressions can include concept names, concept intersection, concept union, complement, existential and universal quantifiers, and individual names.

Definition 1 (ALC Concept Expression). Let NC be a set of concept names and NR a set of role names. The set of ALC concept expressions is the smallest set such that ⊤, ⊥, and every concept name a ∈ NC is an ALC concept description, and if C and D are ALC concept descriptions and R ∈ NR, then CD, CD, ¬C, ∀R.C, and ∃R.C are also ALC concept descriptions.

ALC interpretations can be defined as follows.

Definition 2 (ALC Interpretation). A terminological ALC interpretation I = (ΔI, .I) over a signature (NC, NR, NI) consists of a non-empty set ΔI (domain) and an interpretation function .I, which maps each individual a to an element aI ∈ ΔI, each concept to a subset of ΔI, and each role name to a subset of ΔI × ΔI, such that for all ALC concepts C and D and all role names R, ⊤I = ΔI, ⊥I = ∅, (CD)I = CIDI, (CD)I = CIDI, ¬C = ΔI \ CI , (∃R.C)I = {x ∈ ΔI | There is some y ∈ ΔI with ⟨x, y⟩ ∈ RI and yCI}, and (∀R.C)I = {x ∈ ΔI | For all y ∈ ΔI, if ⟨x, y⟩ ∈ RI, then yCI}.

Since ALC is sufficiently expressive to support many fundamental constructors for web ontologies, it serves as the basis for many slightly more expressive description logics (e.g., ALCHIF, ALCIQ) and most very expressive description logics (SHIF, SHIQ, SHOIN, SROIQ, etc.). Several fragments of ALC are also used, such as logics in the EL, DL-Lite, and FL families, which usually restrict the use of Boolean operators and quantifiers, and consequently their reasoning problems are often easier than that of ALC.