Statistical EL is ExpTime-complete

Bartosz BednarczykBartosz Bednarczyk

Bartosz Bednarczyk
Statistical EL is ExpTime-complete
Information Processing Letters, 169C(106113), August 2021

Details
Bibtex

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}
}