W3C home > Mailing lists > Public > semantic-web@w3.org > January 2008

Complexity of ALCHOI ()

From: Jie Bao <baojie@cs.iastate.edu>
Date: Fri, 25 Jan 2008 01:05:45 -0600
Message-ID: <b6b357670801242305n513e737cqf42ec976633f4672@mail.gmail.com>
To: semantic-web@w3c.org, semantic-web@yahoogroups.com, dl@dl.kr.org

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.

Greets

Jie

-- 
Jie Bao
Department of Computer Science
Iowa State University
http://www.cs.iastate.edu/~baojie
baojie@cs.iastate.edu
515-294-7331(office), 515-509-3927(cell)
Received on Friday, 25 January 2008 07:05:55 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 21:45:20 GMT