<html><head><meta http-equiv="Content-Type" content="text/html charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class=""><br class=""><div><blockquote type="cite" class=""><div class=""><br class=""></div><div class=""><div dir="ltr" class="">Or simplified: is the set selected by p1 equal to the set selected by p2?<br class=""></div></div></blockquote><div><br class=""></div><div>If we allow p1 and p2 to be arbitrary XQuery path expressions, then its undecidable.</div><div>I can reduce the halting problem of Turing machines to this test.</div><br class=""><blockquote type="cite" class=""><div class=""><div class="gmail_extra"><br class=""><div class="gmail_quote">2016-01-27 11:09 GMT+01:00 W.S. Hager <span dir="ltr" class=""><<a href="mailto:wshager@gmail.com" target="_blank" class="">wshager@gmail.com</a>></span>:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr" class="">Isn't the constraint in this case the test: is p2 a subset of p1?<br class=""></div><div class="gmail_extra"><div class=""><div class="h5"><br class=""><div class="gmail_quote">2016-01-27 11:04 GMT+01:00 Pavel Velikhov <span dir="ltr" class=""><<a href="mailto:pavel.velikhov@gmail.com" target="_blank" class="">pavel.velikhov@gmail.com</a>></span>:<br class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class=""><br class="">
> On 27 Jan 2016, at 12:54, W.S. Hager <<a href="mailto:wshager@gmail.com" target="_blank" class="">wshager@gmail.com</a>> wrote:<br class="">
><br class="">
> Can't we formally proof something as obvious Adam's case?<br class="">
<br class="">
</span>In Adam’s case we want to test whether path expression p1 subsumes path expression p2.<br class="">
If we don’t put any conditions on p1 and p2, the problem is undecidable: p1 and p2 may include<br class="">
function calls, so the expressive power of p1 and p2 are that of a Turing Machine.</blockquote></div><br class=""><br clear="all" class=""><br class=""></div></div><span class="">-- <br class=""><div class=""><div class=""><p class=""> 
W.S. Hager<br class="">
Lagua Web Solutions<br class="">
<a href="http://lagua.nl/" target="_blank" class="">http://lagua.nl</a><br class=""></p></div></div>
</span></div>
</blockquote></div><br class=""><br clear="all" class=""><br class="">-- <br class=""><div class="gmail_signature"><div class=""><p class=""> 
W.S. Hager<br class="">
Lagua Web Solutions<br class="">
<a href="http://lagua.nl/" target="_blank" class="">http://lagua.nl</a><br class=""></p></div></div>
</div>
</div></blockquote></div><br class=""></body></html>