Article3071: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Bartosz Bednarczyk (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
Bartosz Bednarczyk (Diskussion | Beiträge) Keine Bearbeitungszusammenfassung |
||
| Zeile 16: | Zeile 16: | ||
|Abstract=We show that the consistency problem for Statistical EL ontologies, defined by Peñaloza and Potyka, is ExpTime-hard. Together with existing ExpTime upper bounds, we conclude ExpTime-completeness of the logic. Our proof goes via a reduction from the consistency problem for EL extended with negation of atomic concepts. | |Abstract=We show that the consistency problem for Statistical EL ontologies, defined by Peñaloza and Potyka, is ExpTime-hard. Together with existing ExpTime upper bounds, we conclude ExpTime-completeness of the logic. Our proof goes via a reduction from the consistency problem for EL extended with negation of atomic concepts. | ||
|Download=BBE-IPL21.pdf | |Download=BBE-IPL21.pdf | ||
|Link=https://www.sciencedirect.com/science/article/abs/pii/S0020019021000272 | |||
|DOI Name=10.1016/j.ipl.2021.106113 | |||
|Forschungsgruppe=Computational Logic | |Forschungsgruppe=Computational Logic | ||
}} | }} | ||
Version vom 7. Mai 2021, 21:15 Uhr
Statistical EL is ExpTime-complete
Bartosz BednarczykBartosz Bednarczyk
Bartosz Bednarczyk
Statistical EL is ExpTime-complete
Information Processing Letters, 169C(106113), August 2021
Statistical EL is ExpTime-complete
Information Processing Letters, 169C(106113), August 2021
- KurzfassungAbstract
We show that the consistency problem for Statistical EL ontologies, defined by Peñaloza and Potyka, is ExpTime-hard. Together with existing ExpTime upper bounds, we conclude ExpTime-completeness of the logic. Our proof goes via a reduction from the consistency problem for EL extended with negation of atomic concepts. - Weitere Informationen unter:Further Information: Link
- Forschungsgruppe:Research Group: Computational LogicComputational Logic
@article{B2021,
author = {Bartosz Bednarczyk},
title = {Statistical {EL} is {ExpTime-complete}},
journal = {Information Processing Letters},
volume = {169C},
number = {106113},
year = {2021},
month = {August},
doi = {10.1016/j.ipl.2021.106113}
}
