Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1]
Spectra of Cardinality Queries over Description Logic Knowledge Bases
Authors: Quentin Manière, Marcin Przybyłko
AAAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Recent works have explored the use of counting queries coupled with Description Logic ontologies. The answer to such a query in a model of a knowledge base is either an integer or , and its spectrum is the set of its answers over all models. While it is unclear how to compute and manipulate such a set in general, we identify a class of counting queries whose spectra can be effectively represented. Focusing on atomic counting queries, we pinpoint the possible shapes of a spectrum over ALCIF ontologies: they are essentially the subsets of N { } closed under addition. For most sublogics of ALCIF, we show that possible spectra enjoy simpler shapes, being Jm, K or variations thereof. To obtain our results, we refine constructions used for finite model reasoning and notably rely on a cycle-reversion technique for the Horn fragment of ALCIF. We also study the data complexity of computing the proposed effective representation and establish the FPNP[log]-completeness of this task under several settings. ... Contributions. We introduce the notion of a spectrum for a CCQ and show that connected and individual-free CCQs evaluated on ALCIF KBs always admit well-behaved spectra, as those are subsets of N closed under addition. We then propose an effective representation of such spectra. ... We further study the data complexity of computing the proposed effective representations of spectra. For many settings, such as concept cardinality queries on ALC KBs, we are able to establish FPNP[log]-completeness of this problem. |
| Researcher Affiliation | Academia | 1Department of Computer Science, Leipzig University, Germany 2Center for Scalable Data Analytics and Artificial Intelligence (Sca DS.AI), Dresden/Leipzig, Germany 3Institute of Informatics, University of Warsaw, Poland EMAIL, EMAIL |
| Pseudocode | No | The paper describes methods and algorithms in prose and uses formal definitions and theorems, but does not contain any explicit pseudocode blocks or algorithm listings. |
| Open Source Code | No | An appendix with full proofs can be found in the long version of this paper, see (Mani ere and Przybyłko 2024). |
| Open Datasets | No | The paper is theoretical and focuses on Description Logic Knowledge Bases. It uses abstract examples and does not mention or utilize any specific publicly available datasets for empirical evaluation. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with datasets. Therefore, no dataset splits are mentioned. |
| Hardware Specification | No | The paper is a theoretical work focusing on logical properties and complexity. It does not describe any experimental setup or mention specific hardware used. |
| Software Dependencies | No | The paper is theoretical and does not discuss implementation details or list specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is a theoretical work and does not describe an experimental setup, hyperparameters, or training configurations. |