W3C home > Mailing lists > Public > public-rif-wg@w3.org > April 2006

Re: [RIF][UCR] Decidability a requirement?

From: Dave Reynolds <der@hplb.hpl.hp.com>
Date: Fri, 07 Apr 2006 09:14:28 +0100
Message-ID: <44361F64.5030805@hplb.hpl.hp.com>
To: Christian de Sainte Marie <csma@ilog.fr>
CC: RIF WG <public-rif-wg@w3.org>

Christian de Sainte Marie wrote:

> 
> Christian de Sainte Marie wrote:
> 
>>
>> [...]  we encourage you to
>> propose, on this medium, arguments in favor or against making 
>> decidability a requirement for all or part of the RIF.
> 
> 
> [Chair's hat off]
> 
> Decidability, in the sense that "RIF allows only the expression of rules 
> or rulesets that are decidable wrt any RIF expression", has nothing to 
> do with requirements or design constraints for the RIF, IMHO (or: didn't 
> we decide that it was "le RIF"?).
> 
> If a rule language covered by the RIF is decidable (in the same sense, 
> mutatis mutandis), then it will be able to produce or consume only 
> decidable RIF rulesets (decidable wrt expressions in that same rule 
> language). If all the rule languages covered by the RIF are decidable, 
> then only decidable rulesets will ever be actually expressed in the RIF 
> (used as a RIF; and decidable wrt expressions in the rule languages that 
> produce/consume each of these rulesets, resp.).
> 
> None of the above requires that the RIF itself should be decidable.

Consider the problem of a person implementing a translator from RIF to 
their own rule language. If their rule language is decidable (e.g. it is a 
datalog engine) and there is *no* RIF dialect which is decidable then they 
cannot implement RIF, period. They could implement a subset of some nearby 
dialect but I presume the point of a dialect is to achieve interoperability 
between some subset of rule languages and partial implementations fail to 
achieve that.

The question is not "should RIF be decidable", clearly there must be RIF 
dialects which are undecidable.

The question is "should RIF Core be decidable". As far as I can understand 
the charter and the term "extension", if RIF Core is undecidable then *all* 
RIF dialects are undecidable which doesn't seem ideal.

If RIF core is undecidable then either:

(a) the "extension" mechanism needs to include narrowings/constraints which 
can reduce the expressibility of the core; and/or

(b) there needs to be some mechanism other than RIF Dialect (as described 
on the terminology page) for subsetting RIF so that a provider can scope 
the RIF fragment they are using narrowly enough that consumers know that 
they can provide a complete implementation.

Dave
Received on Friday, 7 April 2006 08:48:06 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 2 June 2009 18:33:28 GMT