The Price of Selfishness: Conjunctive Query Entailment for ALCSelf Is 2EXPTIME-Hard
Authors: Bartosz Bednarczyk, Sebastian Rudolph5495-5502
AAAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | As common for this type of problem, our proof establishes a reduction from alternating Turing machines running in exponential space, but several novel ideas and encoding tricks are required to make the approach work in that specific, restricted setting. |
| Researcher Affiliation | Academia | Bartosz Bednarczyk,1,2 Sebastian Rudolph1 1 Computational Logic Group, Technische Universität Dresden, Germany 2 Institute of Computer Science, University of Wrocław, Poland { bartosz bednarczyk, sebastian.rudolph }@tu-dresden.de |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper is theoretical and does not describe a software methodology for which code would be provided. |
| Open Datasets | No | The paper is theoretical and does not use datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments that would involve validation splits. |
| Hardware Specification | No | The paper is theoretical and does not mention any specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers for reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |