W3C home > Mailing lists > Public > semantic-web@w3.org > March 2007

Re: How to derive a consistent set of FOL constraints

From: Enrico Franconi <franconi@inf.unibz.it>
Date: Tue, 6 Mar 2007 11:35:02 +1100
Message-Id: <6D5B7655-CE31-43D1-9295-8560012FF8B9@inf.unibz.it>
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
To: "John F. Sowa" <sowa@bestweb.net>

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:49 GMT

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