Learning Description Logic Concepts: When can Positive and Negative Examples be Separated?
Authors: Maurice Funk, Jean Christoph Jung, Carsten Lutz, Hadrien Pulcini, Frank Wolter
IJCAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the fundamental question of when a separating DL concept exists and provide useful model-theoretic characterizations as well as complexity results for the associated decision problem. For expressive DLs such as ALC and ALCQI, our characterizations show a surprising link to the evaluation of ontology-mediated conjunctive queries. We exploit this to determine the combined complexity (between EXPTIME and NEXPTIME) and data complexity (second level of the polynomial hierarchy) of separability. |
| Researcher Affiliation | Academia | Maurice Funk1 , Jean Christoph Jung1 , Carsten Lutz1 , Hadrien Pulcini2 and Frank Wolter2 1Department of Computer Science, University of Bremen 2Department of Computer Science, University of Liverpool |
| Pseudocode | No | The paper provides theoretical characterizations and complexity analysis but does not include any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper discusses various DL concept learning systems (e.g., DL LEARNER) and related work, but it does not provide any statement or link indicating that the authors have released open-source code for their own described methodology. |
| Open Datasets | No | This is a theoretical paper that focuses on complexity analysis and model-theoretic characterizations, and therefore does not use or reference any datasets for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper focusing on model-theoretic characterizations and complexity analysis. It does not involve empirical experiments or dataset splits for training, validation, or testing. |
| Hardware Specification | No | This is a theoretical paper that does not involve empirical experiments requiring specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper does not mention any specific software dependencies or their version numbers, as it is a theoretical work on logic and complexity and does not describe software implementations. |
| Experiment Setup | No | As a theoretical paper focused on model-theoretic characterizations and complexity, it does not describe any empirical experimental setup, hyperparameters, or training configurations. |