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

Bijan Parsia wrote:
> 
> 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.
> 
> 

I thought about encoding the problem of a Venn diagram of six triangles 
in OWL, as an extra credit test case. It felt possible, but with more 
effort than I wanted to spend on it.

A few years ago, I wrote custom code for this problem which took months 
to execute. Specific parts of the custom code which I suspect is hard in 
the general case is suppression of automorphisms (see nauty). I think 
that general code is very likely to keep proving the same thing time and 
time again, with minor relabelling differences.

i.e. a first step in automorphism optimization would be to take an 
appropriate, cheap to compute, closure of the input graph and compute 
its automorphism group (including allowing mapping named resources to 
named resources, not just bnode mapping). The rest of the search should 
then proceed informed by the automorphism group, to reduce the workload.

Jeremy

Received on Wednesday, 11 January 2006 15:14:49 UTC