Author:
Nguyen, Linh Anh ( Warsaw University)
Szalas, Andrzej (Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab) (Linköping University, The Institute of Technology)
Title:
Checking Consistency of an ABox w.r.t. Global Assumptions in PDL
Department:
Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab
Linköping University, The Institute of Technology
Publication type:
Article in journal (Refereed)
Publisher:
IOS Press
In:
Fundamenta Informaticae(ISSN 0169-2968)
URI:
urn:nbn:se:liu:diva-62154
Permanent link:
http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-62154
Subject category:
Engineering and Technology
Abstract(en)
:
We reformulate Pratts tableau decision procedure of checking satisfiability of a set of formulas in PDL. Our formulation is simpler and its implementation is more direct. Extending the method we give the first Ex PT m E (optimal) tableau decision procedure not based on transformation for checking consistency of an ABox w.r.t. a TBox in PDL (here, PDL is treated as a description logic). We also prove a new result that the data complexity of the instance checking problem in PDL is coNP-complete.
Available from:
2010-11-19
Statistics:
6 hits