From: Markus Krötzsch <mak@aifb.uni-karlsruhe.de>

Date: Tue, 25 Jul 2006 19:21:21 +0200

To: Francois Bry <bry@ifi.lmu.de>

Cc: "Public-Rif-Wg (E-mail)" <public-rif-wg@w3.org>

Message-Id: <200607251921.33642.mak@aifb.uni-karlsruhe.de>

Date: Tue, 25 Jul 2006 19:21:21 +0200

To: Francois Bry <bry@ifi.lmu.de>

Cc: "Public-Rif-Wg (E-mail)" <public-rif-wg@w3.org>

Message-Id: <200607251921.33642.mak@aifb.uni-karlsruhe.de>

On Tuesday 25 July 2006 15:48, Francois Bry wrote: > Dear RIFler, > > Hier are a few comments to Axel's very good proposal: > > Axel's proposed RIFRAF questionnaire (for evaluating/populating the > > framework): [http://www.w3.org/2002/09/wbs/38457/RAFQuestionnaire/] > > The following question under 3.1 seems to me ambigous: "Is your language > decidable?" Decidability of a language usually means, at least in > theoretical Computer Science, that whether a word (= program) belongs to > the language is decidable.This is the case for all programming and > modelling languages. My understanding is that Axel would like to ask > instead whether the termination of programs is decidable. I agree. Since there was some confusion in the July 25 telco, here is some clarification and a proposal for fixing this. (1) "Deciding a language" is an established term in (theoretical) Computer Science. It means: "deciding whether some word belongs to the language" (you may have encountered this meaning if you ever heard about regular, context-free etc. grammars). (2) "Decidability of some logical or computational formalism" usually refers to some *inference problem* or *reasoning task* for the language. So you do not "decide the formal (rule) language", but you decide some inference problem related to this language. [Side remark: of course this can also be comprehended as deciding some related "language" in a Computer Science sense, but this is not relevant here.] So every language we deal with is probably decidable in the sense of (1). What we are interested in the questionaire is whether its "main" inference problem is decidable in the sense of (2). The problem was that the wording of 3.1 is ambiguous about the fact that we mean (2) and that it does not say which computation/reasoning task we are really interested in when asking for complexity and decidability. So it is necessary to add some small note to 3.1 to clarify what decidability (and also the other items) refer to. I think this could be sufficiently fixed by changing the original text """Specify Expressivity of your language, e.g. Turing-completeness, or complexity classes for decidable languages. Please give complexity results if availbale (hardness, membership, completeness) * Is your language Turing-complete? * Is your language decidable? * Is your language semi-decidable? * Other expressivity/decidability results (specify) """ to """Specify expressivity of your language by describing the class of expressible computations and/or the difficulty of typical inferencing tasks. Give details in the text field below if it is not obvious what computation/inference task you refer to. Please also give more specific complexity results (e.g. hardness, membership, completeness) if available. * Is the rule formalism Turing-complete? * Is inferencing for your language decidable? * Is inferencing for your language semi-decidable (but not decidable)? * Other expressivity/decidability results (specify) """ Precision comes at the price of a more complicated wording here, since we have to account for Turing-completeness and for (semi-)decidability. Read on for some thoughts on this issue. Anyway, the above completes my ACTION from telco July 25. ------ As a second remark, I suggest to add one item * Is inferencing for your language not even semi-decidable? since this applies to some of the discussed rule-languages (e.g. WRL) as well, and it would otherwise not be obvious what to answer in such a case. ------ Thirdly, another remark emerges from the above suggestion. We apparently ask for different things when putting "Turing-completeness" and "semi-decidability" into one question. * Turing completeness refers to the ability of a formalism to express certain functions (actually: all "algorithmically computable" partial functions). * Semi-decidability refers to the difficulty of answering certain yes/no-questions (e.g. the question whether something is entailed by a rule spec). Semi-decidability of such a task asserts that, whenever the answer is "yes", this answer can be computed. It does not assert anything for the cases where the answer would be "no". Turing-completeness is related to semi-decidability via the halting problem that Francois mentioned. The yes/no-question there is: "Will the formalism ever return a result for this input?" (recall that we may compute *partial* functions as well). So Turing-completeness typically applies to formalisms that compute something, and in this case is mostly synonymous with semi-decidability of the halting problem. On the other hand, expressive logics can also (indirectly) describe computations on Turing machines, and thus might be considered Turing-complete in this sense. So I wonder whether there we have any shared understanding about the meaning of "Turing-complete" in the above question. Do we mean * "somehow able to simulate the computation of any Turing machine" or, more strictly, * "using rules to represent functions, and being able to represent (at least) all Turing-computable functions"? The first is mostly synonymous with being semi-decidable, the second combines aspects of expressivity with the question *what* actually is expressed. Neither is really desirable here. I therefore would suggest to make Turing-completeness less prominent by making it a sub-case of the item for semi-decidability (possibly giving the same wording as above, but sharing one check-box with semi-decidability). This should yield the same (and probably more consistent/accurate) information about the classified rule language, but it eliminates the different combinations of answers that could otherwise occur. Regards, Markus > > Convcering 3.2, I would suggest ot ask whether the model theory is > defined in a Tarskyan style, i.e. by means of a valuation function > recursively defined on a formulas (or program expression) strucure like > classical logic models or by some other manes like well-founded or > stable models. This distinction is essential for the evaluation of a > rule-based language. Basically: rule languages with a Tarskyan model > theory are "easy" to evaluate. > > I would suggest to add a question whether the language has means to > access data in Web formats such as HTML, XML, RDF, OWL data. > > Regards, > > Francois -- Markus Krötzsch Institute AIFB, University of Karlsruhe, D-76128 Karlsruhe mak@aifb.uni-karlsruhe.de phone +49 (0)721 608 7362 www.aifb.uni-karlsruhe.de/WBS/ fax +49 (0)721 693 717Received on Tuesday, 25 July 2006 17:21:48 GMT

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