The Projection Problem for EL Actions

Hongkai LiuHongkai Liu, Carsten LutzCarsten Lutz, Maja MilicicMaja Milicic

Download

Hongkai Liu, Carsten Lutz, Maja Milicic
The Projection Problem for EL Actions
Proceedings of the 2008 International Workshop on Description Logics (DL2008), volume 353 of CEUR-WS, 2008

Details
Bibtex

KurzfassungAbstract
In this paper, we investigate the complexity of executability and projection in EL and the extension of EL with atomic negation. In both cases, we allow for negated assertions in the post-conditions of actions. Our results show that, in general, tractability does not transfer from instance checking in EL to executability and projection. Even in EL without TBoxes, the latter problems are co-NP-hard. This is due to two sources of intractability: (1) existential restrictions in the initial ABox together with negated assertions in post-conditions; and (2) conditional post-conditions. We prove a matching co-NP upper bound for EL with atomic negation. We also show that, in the presence of acyclic TBoxes, projection in EL is PSpace-hard and thus not easier than in ALC. Finally, we identify restrictions under which executability and projection in EL w.r.t. acyclic TBoxes can be decided in polynomial time.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ LiLuMi-DL-08,
  author = {Hongkai {Liu} and Carsten {Lutz} and Maja {Milicic}},
  booktitle = {Proceedings of the 2008 International Workshop on Description Logics ({DL2008})},
  series = {CEUR-WS},
  title = {The Projection Problem for $\mathcal{EL}$ Actions},
  volume = {353},
  year = {2008},
}