Research map / Learning theory and algorithms / Combinatorial and search optimization

Spectra of Cardinality Queries over Description Logic Knowledge Bases

AAAI 2025 · Learning theory and algorithms › Combinatorial and search optimization · approach: Logic and answer set programming theory · 1 citations (OpenAlex)

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.

Characterizes the possible spectra (sets of achievable answer counts, in N∪{∞}) of atomic counting queries over DL knowledge bases, for ALCIF and its sublogics, and studies the data complexity of computing effective representations.

Problem

Which sets of integers (with infinity) can be the spectrum of a counting query over all models of a description logic knowledge base, and how can such spectra be represented effectively and computed?

Approach

Shows that spectra of connected, individual-free counting CQs are additively closed subsets of N∪{∞}, that every such subset is realizable for concept cardinality queries over ALCIF, and that simpler shapes (intervals [m,∞] or variants) arise for most sublogics; for ELIFbot it uses a refined cycle-reversion technique from finite model reasoning.

Key results

• For ALCIF, a non-trivial subset of N∪{∞} is concept-realizable iff it is a subsemigroup containing ∞.
• For ALCI and ALCF, realizable spectra are exactly [[M,∞]] or {0}∪[[M,∞]].
• For ELIFbot, every realizable non-trivial spectrum has shape {∞}, {0,∞}, or S∪[[M,∞]] with S ⊆ [[0,M]]; a spectrum {4}∪[[6,∞]] is realized.

Surprising findings

• Spectra for ELIFbot can have non-trivial finite exceptional parts (e.g., {4}∪[[6,∞]]), unlike the simpler shapes for other sublogics.
• Expressive ALCIF realizes every additively closed subset of N∪{∞}, including periods larger than 1, which requires functional and inverse-functional roles together.

Limitations

• Results are restricted to atomic (concept and role cardinality) counting queries; general counting CQs are only partly covered.
• Full characterization of spectra is open for some sublogics and for role cardinality queries with challenging shapes.

Experimental setup

Builds on: finite model reasoning cycle reversion ontology-mediated query answering ALCIF description logic

Closest papers by meaning

• Description Logics with Two Types of Definite Descriptions: Complexity, Expressiveness, and Automated Deduction (AAAI 2026 · similarity 0.89)
• Finite Entailment of Local Queries in the Z Family of Description Logics (AAAI 2022 · similarity 0.88)
• The Price of Selfishness: Conjunctive Query Entailment for ALCSelf Is 2EXPTIME-Hard (AAAI 2022 · similarity 0.88)
• Answering Conjunctive Queries with Safe Negation and Inequalities over RDFS Knowledge Bases (AAAI 2025 · similarity 0.87)
• Consistent Query Answering over Existential Rules with Open and Closed Predicates (AAAI 2025 · similarity 0.86)
• Stable Model Semantics for Description Logic Terminologies (AAAI 2024 · similarity 0.86)