The Complexity of Subsumption in Fuzzy EL
Authors: Stefan Borgwardt, Marco Cerami, Rafael Peñaloza
IJCAI 2015 | Venue 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 EMAIL Marco Cerami Department of Computer Science Palacký University in Olomouc Czech Republic EMAIL Rafael Peñaloza KRDB Research Centre Free University of Bozen-Bolzano Italy EMAIL |
| 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. |