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

Re: Constraint-based inference? (was Re: Solving Sudoku with OWL)

From: Bijan Parsia <bparsia@isr.umd.edu>
Date: Wed, 11 Jan 2006 08:39:29 -0500
Message-Id: <397e1b604eb78ca3ceb8ec7216bd646b@isr.umd.edu>
To: semantic-web@w3.org

Danny Ayers wrote:
> The Sudoku thread reminds me of a question (prompted by a comment from
> Tim Finin [1]) - has anyone tried doing any RDFS/OWL inference based
> on a constraints programming engine [2]?

Tableau reaosners are reasonably thought of as a constraints engine. 
Indeed, you'll see in the mid 90s literature that the completion graph 
is often referred too as a "constraint system". Optimizations are 
related (see "backjumping" for example).

I supposes it's constraints over a boolean domain.

> For highly combinative problems (like Sudoku) perhaps such a setup may
> give improved performance

I very very much doubt it. Plus care would be required to ensure a 
decision procedure.

>  (maybe a hybrid might be feasible - e.g. the
> constraints part sorting out the AllDifferent kind of inferences, then
> passing the partial results to a complete DL reasoner to finish up..?)

I don't think this makes sense. All AllDifferent does is establish 
inequalities. In the completion graph, this means that if you try to 
merge two such nodes (due to a max cardinality) you'll get a clash.

In general, I'd caution against these sorts of hopes. It's not 
impossible that some other field has done some simply amazing work and 
has super tuned somethings that we could just lift.....but I doubt it 
:)

A different questions is where existing constraint solvers solve 
certain problems very fast that have straightforward and simple OWL 
equivalents that existing reasoners don't handle that well. If you 
could show that equivalence, you could simply map the OWL to the 
constraints language, solve, and map the answers back. I suspect, 
however, that there many interesting cases.

Cheers,
Bijan.
Received on Wednesday, 11 January 2006 13:39:31 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 19:47:11 UTC