Description Logic

Origin. Evolved from semantic networks and frame systems (1970s-80s). KL-ONE (Brachman & Schmolze, 1985) was influential. The "description logic" family formalized with attention to computational complexity. Foundation for OWL (Web Ontology Language) and the Semantic Web. Balances expressiveness with decidability.

Models. Concepts (classes), roles (relations), and individuals. Ontologies defining what kinds of things exist and how they relate. "A parent is a person with at least one child." Knowledge representation with formal semantics and decidable reasoning: subsumption, consistency, instance checking.

Formalism.

Basic elements:

Concepts: classes/types (Person, Animal, ...)
Roles: binary relations (hasChild, worksFor, ...)
Individuals: named objects (john, mary, ...)

Concept constructors (ALC and extensions):

Syntax	Name	Semantics
A	Atomic concept	A^I ⊆ Δ^I
⊤	Top	Δ^I (everything)
⊥	Bottom	∅ (nothing)
¬C	Negation	Δ^I \ C^I
C ⊓ D	Intersection	C^I ∩ D^I
C ⊔ D	Union	C^I ∪ D^I
∀r.C	Value restriction	{x \| ∀y. (x,y)∈r^I → y∈C^I}
∃r.C	Existential	{x \| ∃y. (x,y)∈r^I ∧ y∈C^I}
≥n r.C	At-least	{x \| \|{y \| (x,y)∈r^I ∧ y∈C^I}\| ≥ n}
≤n r.C	At-most	{x \| \|{y \| (x,y)∈r^I ∧ y∈C^I}\| ≤ n}

DL naming convention:

AL: attributive language (basic)
C: complement (full negation)
E: existential quantification
N: number restrictions
Q: qualified number restrictions
H: role hierarchies
O: nominals (individuals in concepts)
I: inverse roles
S: ALC + transitive roles

Example: SHOIN (basis for OWL-DL)

Knowledge base:

TBox: terminological axioms (C ⊑ D, C ≡ D)
ABox: assertional axioms (C(a), r(a,b))
RBox: role axioms (r ⊑ s, transitivity)

Reasoning tasks:

Concept satisfiability: is C consistent?
Subsumption: does C ⊑ D hold?
Instance checking: is a ∈ C?
Consistency: is the KB satisfiable?
Classification: compute full subsumption hierarchy

Symbols.

Symbol	Unicode	Name	Meaning
⊤	U+22A4	Top	Universal concept
⊥	U+22A5	Bottom	Empty concept
⊓	U+2293	Intersection	Concept and
⊔	U+2294	Union	Concept or
¬	U+00AC	Complement	Concept negation
∀	U+2200	Value restriction	All related are
∃	U+2203	Existential	Some related is
⊑	U+2291	Subsumption	Subclass of
≡	U+2261	Equivalence	Same extension
≥n, ≤n	—	Number restriction	Cardinality bounds

Metatheory. ALC is EXPTIME-complete. Adding features increases complexity: SHOIN is NEXPTIME-complete. Decidability is preserved by careful design; arbitrary first-order features break it. Tableau algorithms are standard: build a model or find contradiction. OWL 2 profiles (EL, RL, QL) trade expressiveness for polynomial reasoning.

Applies to. Ontology engineering (Protégé, OWL). Semantic Web. Biomedical ontologies (SNOMED CT, Gene Ontology). Knowledge graphs. Data integration. Conceptual modeling. Query answering over ontologies.

Limitations. Trade-off: more expressive = harder to reason. No rules, no recursion (extensions like DL-safe rules address this). Closed-world vs open-world: DLs use open-world assumption (absence doesn't mean falsity). Large ABoxes challenge scalability. Unique name assumption often needed. Non-experts find DL syntax opaque.