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.

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

Definition 2 (ALC Interpretation). A terminological ALC interpretation I = (Δ^I, ^.I) over a signature (N_C, N_R, N_I) consists of a non-empty set Δ^I (domain) and an interpretation function ^.I, which maps each individual a to an element a^I ∈ Δ^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 = ∅, (C ⊓ D)^I = C^I ∩ D^I, (C ⊔ D)^I = C^I ∪ D^I, ¬C = Δ^I \ C^I , (∃R.C)^I = {x ∈ Δ^I | There is some y ∈ Δ^I with ⟨x, y⟩ ∈ R^I and y ∈ C^I}, and (∀R.C)^I = {x ∈ Δ^I | For all y ∈ Δ^I, if ⟨x, y⟩ ∈ R^I, then y ∈ C^I}.

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.