Cardinality Queries over DL-Lite Ontologies
Authors: Meghyn Bienvenu, Quentin Manière, Michaël Thomazo
IJCAI 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | While we prove that cardinality query answering is tractable (TC0) in data complexity when the ontology is formulated in DL-Litecore, the problem becomes co NP-hard as soon as role inclusions are allowed. For DL-Lite H pos (which allows only positive axioms), we establish a P-co NP dichotomy and pinpoint the TC0 cases; for DL-Lite H core (allowing also negative axioms), we identify new sources of co NP complexity and also exhibit L-complete cases. |
| Researcher Affiliation | Academia | Meghyn Bienvenu1 , Quentin Mani ere1 and Micha el Thomazo2 1CNRS, University of Bordeaux, Bordeaux INP, La BRI, Talence, France 2Inria, DI ENS, ENS, CNRS, University PSL, Paris, France |
| Pseudocode | No | The paper describes theoretical concepts and methods but does not include any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not mention or provide access to any open-source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments with datasets, thus it does not mention public training data availability. |
| Dataset Splits | No | The paper is theoretical and does not conduct experiments with datasets, thus it does not mention training/validation/test splits. |
| Hardware Specification | No | As a theoretical paper, it does not describe any hardware specifications used for experiments. |
| Software Dependencies | No | As a theoretical paper, it does not list specific software dependencies with version numbers. |
| Experiment Setup | No | As a theoretical paper, it does not detail an experimental setup, hyperparameters, or training configurations. |