Research map / Large language models / Agents, code and math
Stable Model Semantics for Description Logic Terminologies
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Defines a stable model semantics for DL knowledge bases and cyclic terminologies via Quantified Equilibrium Logic, proves undecidability for minimal-model reasoning in ALCIO and EXPTIME-completeness of reasoning for ALCI terminologies.
Problem
Classical DL semantics lacks default negation and well-founded justification for cyclic terminology definitions, and the CWA/OWA combination is unnatural; a semantics with decidable, tractable reasoning is needed.
Approach
Derive a stable model semantics for DLs from Quantified Equilibrium Logic, with base predicates treated as fixed (non-minimized) and defined concepts minimized; for terminologies, equivalent characterizations via level mappings and fixpoints, and a tree-model-property plus two-way alternating tree automata decision procedure.
Key results
- Concept satisfiability in minimal models of ALCIO KBs is undecidable, implying undecidability of standard reasoning under stable model semantics for ALCI KBs.
- Satisfiability, concept subsumption, and concept satisfiability for ALCI terminologies under the stable model semantics are EXPTIME-complete.
- The three definitions (equilibrium logic, level mappings, fixpoint computation) of stable models for terminologies are shown equivalent (Theorem 4).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply the stable model semantics to ALCI terminologies | ALCI terminologies · Concept satisfiability, subsumption, and stable-model existence | computational complexity: EXPTIME-complete | Mixed |
| Use stable model semantics for general ALCI knowledge bases | ALCI knowledge bases · Standard reasoning problems | decidability: decidable -> undecidable | Hurt |
| Minimize predicates in ALCIO knowledge bases | ALCIO knowledge bases · Concept satisfiability in minimal models | decidability: undecidable | Hurt |
| Use the stable model semantics for ALCI terminologies rather than general knowledge bases | ALCI terminologies · Reasoning compared with classical semantics | computational complexity: EXPTIME-complete | No clear effect |
Surprising findings
- Stable model semantics for ALCI terminologies loses the finite model property enjoyed by classical ALCI semantics (Example 4 has only infinite stable models).
- Under the stable model semantics, standard reasoning for general ALCI KBs is undecidable, unlike classical ALCI.
Limitations
- General ALCI/ALCIO KB reasoning is undecidable under the stable model semantics.
- Complexity results are established for ALCI terminologies only; extension to ALCIO left as future work.
- Finite model reasoning under the stable model semantics is left open.
Experimental setup
Baselines: descriptive semantics least fixpoint semantics (Baader 1990) MKNF-based DL semantics TGD stable model semantics (Gottlob et al. 2021)
Builds on: Quantified Equilibrium Logic Answer Set Programming stable model semantics circumscription in DLs least fixpoint semantics of Baader (1990)
Closest papers by meaning
- Description Logics with Two Types of Definite Descriptions: Complexity, Expressiveness, and Automated Deduction (AAAI 2026 · similarity 0.88)
- Extending Description Logics with Generic Concepts – the Case of Terminologies (AAAI 2026 · similarity 0.88)
- Finite Entailment of Local Queries in the Z Family of Description Logics (AAAI 2022 · similarity 0.87)
- Spectra of Cardinality Queries over Description Logic Knowledge Bases (AAAI 2025 · similarity 0.86)
- An Alternative Theory of Stable Revision for Nondeterministic Approximation Fixpoint Theory and the Relationships (AAAI 2025 · similarity 0.84)
- Answering Conjunctive Queries with Safe Negation and Inequalities over RDFS Knowledge Bases (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.