- From: Enrico Franconi <franconi@inf.unibz.it>
- Date: Tue, 6 Mar 2007 11:35:02 +1100
- To: "John F. Sowa" <sowa@bestweb.net>
- Cc: Ontology Summit 2007 Forum <ontology-summit@ontolog.cim3.net>, lobrst@mitre.org, ezolin@cs.man.ac.uk, public-owl-dev@w3.org, matthew.williams@cancer.org.uk, semantic-web@w3.org
On 6 Mar 2007, at 08:31, John F. Sowa wrote: > To continue my point that efficiency *always* depends > on what you're trying to do, I would like to address the > problem of finding a consistent set of constraints: > > > I, as usual, recommend the > > description logic complexity navigator: > > http://www.cs.man.ac.uk/~ezolin/logic/complexity.html > > Given a set of arbitrary first-order constraints, the problem > of proving consistency is NP complete. Well, it seems to me: 1) the problem of checking consistency (i.e., finding the existence of a model) of an arbitrary FOL formula is not decidable; 2) the problem of checking that a FOL formula is true in an interpretation (i.e., that a DB is consistent wrt a set of FOL constraints) is PSPACE-complete in *combined* complexity (i.e, wrt the size of the constraints and the DB), while it is in PTIME in *data* complexity (i.e., wrt the size of the DB only); 3) according to the abovementioned DL complexity navigator, the problem of checking consistency of DL KBs is most of the time decidable. cheers --e.
Received on Tuesday, 6 March 2007 00:35:53 UTC