[DL] Complexity of ALCHOI (¬)

Jie Bao baojie at cs.iastate.edu
Fri Jan 25 08:05:45 CET 2008

Dear friends:

I wonder if  the complexity of the DL ALCHOI (¬), i.e. ALCHOI with
negations on roles is already  known. I know it should be ExpTime-hard
(harder on ALCIO) and in NExpTime (since it is a subset of ALBO). I
wish to know the gap between these two has already been explored.
Thank you in advance for your concern.



Jie Bao
Department of Computer Science
Iowa State University
baojie at cs.iastate.edu
515-294-7331(office), 515-509-3927(cell)

More information about the dl mailing list