Abstract: We consider the problem of deciding, given an instance query A(x), an EL-TBox T , and possibly an ABox signature Σ, whether A(x) is FO-rewritable relative to T and Σ-ABoxes. Our main results are PSPACE-completeness for the case where Σ comprises all symbols and EXPTIME-completeness for the general case. We also show that the problem is in PTIME for classical TBoxes and that every instance query is FO-rewritable into a polynomial-size FO query relative to every (semi)-acyclic TBox (under some mild assumptions on the data).
Publication Year: 2012
Publication Date: 2012-06-01
Language: en
Type: preprint
Access and Citation
Cited By Count: 12
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot