The Complexity of Subsumption in Fuzzy EL
Authors: Stefan Borgwardt, Marco Cerami, Rafael Peñaloza
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we prove that EL under finitely valued semantics is EXPTIME-complete whenever the Łukasiewicz t-norm is included in the semantics. This proves a dichotomy similar to one that exists for infinitely valued FDLs [Borgwardt et al., 2015b] since, for all other finitely valued chains of truth values, reasoning in fuzzy EL can be shown to be in PTIME using the methods from [Mailis et al., 2012]. The relevance of our result goes beyond the computational aspect. |
| Researcher Affiliation | Academia | Stefan Borgwardt Chair for Automata Theory Technische Universität Dresden Germany Stefan.Borgwardt@tu-dresden.de Marco Cerami Department of Computer Science Palacký University in Olomouc Czech Republic marco.cerami@upol.cz Rafael Peñaloza KRDB Research Centre Free University of Bozen-Bolzano Italy rafael.penaloza@unibz.it |
| Pseudocode | No | The paper contains mathematical proofs and logical reductions but no structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper mentions a technical report for full proofs but does not provide or link to any open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve training models on datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve dataset splits for validation. |
| Hardware Specification | No | This is a theoretical paper and does not describe hardware used for experiments. |
| Software Dependencies | No | This is a theoretical paper and does not list software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | This is a theoretical paper and does not provide details about an experimental setup or hyperparameters. |