[xquery-talk] Function for determining one XPath as subset of another

W.S. Hager wshager at gmail.com
Wed Jan 27 02:17:31 PST 2016


Indeed, the expressions should terminate.

2016-01-27 11:11 GMT+01:00 Pavel Velikhov <pavel.velikhov at gmail.com>:

>
>
> Or simplified: is the set selected by p1 equal to the set selected by p2?
>
>
> If we allow p1 and p2 to be arbitrary XQuery path expressions, then its
> undecidable.
> I can reduce the halting problem of Turing machines to this test.
>
>
> 2016-01-27 11:09 GMT+01:00 W.S. Hager <wshager at gmail.com>:
>
>> Isn't the constraint in this case the test: is p2 a subset of p1?
>>
>> 2016-01-27 11:04 GMT+01:00 Pavel Velikhov <pavel.velikhov at gmail.com>:
>>
>>>
>>> > On 27 Jan 2016, at 12:54, W.S. Hager <wshager at gmail.com> wrote:
>>> >
>>> > Can't we formally proof something as obvious Adam's case?
>>>
>>> In Adam’s case we want to test whether path expression p1 subsumes path
>>> expression p2.
>>> If we don’t put any conditions on p1 and p2, the problem is undecidable:
>>> p1 and p2 may include
>>> function calls, so the expressive power of p1 and p2 are that of a
>>> Turing Machine.
>>
>>
>>
>>
>> --
>>
>> W.S. Hager
>> Lagua Web Solutions
>> http://lagua.nl
>>
>
>
>
> --
>
> W.S. Hager
> Lagua Web Solutions
> http://lagua.nl
>
>
>


-- 

W.S. Hager
Lagua Web Solutions
http://lagua.nl
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://x-query.com/pipermail/talk/attachments/20160127/8128cd2a/attachment.html>


More information about the talk mailing list