<div dir="ltr">There's the notion of co-inductive types. I think in Haskell you could proof the case, so why not in xquery?<br></div><div class="gmail_extra"><br><div class="gmail_quote">2016-01-27 11:24 GMT+01:00 Pavel Velikhov <span dir="ltr"><<a href="mailto:pavel.velikhov@gmail.com" target="_blank">pavel.velikhov@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><br><div><span class=""><blockquote type="cite"><br><div><div dir="ltr">Indeed, the expressions should terminate.<br></div></div></blockquote><div><br></div></span><div>Since you can include a function call in your path expression, and you can include your own custom function, there is</div><div>no guarantee that the expression will terminate.</div><div><br></div><div>I.e. you need to take a subset of possible path expression already, in general case the problem is undecidable.</div><span class=""><br><blockquote type="cite"><div><div class="gmail_extra"><br><div class="gmail_quote">2016-01-27 11:11 GMT+01:00 Pavel Velikhov <span dir="ltr"><<a href="mailto:pavel.velikhov@gmail.com" target="_blank">pavel.velikhov@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word"><br><div><span><blockquote type="cite"><div><br></div><div><div dir="ltr">Or simplified: is the set selected by p1 equal to the set selected by p2?<br></div></div></blockquote><div><br></div></span><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><span><br><blockquote type="cite"><div><div class="gmail_extra"><br><div class="gmail_quote">2016-01-27 11:09 GMT+01:00 W.S. Hager <span dir="ltr"><<a href="mailto:wshager@gmail.com" target="_blank">wshager@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Isn't the constraint in this case the test: is p2 a subset of p1?<br></div><div class="gmail_extra"><div><div><br><div class="gmail_quote">2016-01-27 11:04 GMT+01:00 Pavel Velikhov <span dir="ltr"><<a href="mailto:pavel.velikhov@gmail.com" target="_blank">pavel.velikhov@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span><br>
> On 27 Jan 2016, at 12:54, W.S. Hager <<a href="mailto:wshager@gmail.com" target="_blank">wshager@gmail.com</a>> wrote:<br>
><br>
> Can't we formally proof something as obvious Adam's case?<br>
<br>
</span>In Adam’s case we want to test whether path expression p1 subsumes path expression p2.<br>
If we don’t put any conditions on p1 and p2, the problem is undecidable: p1 and p2 may include<br>
function calls, so the expressive power of p1 and p2 are that of a Turing Machine.</blockquote></div><br><br clear="all"><br></div></div><span>-- <br><div><div><p> 
W.S. Hager<br>
Lagua Web Solutions<br>
<a href="http://lagua.nl/" target="_blank">http://lagua.nl</a><br></p></div></div>
</span></div>
</blockquote></div><br><br clear="all"><br>-- <br><div><div><p> 
W.S. Hager<br>
Lagua Web Solutions<br>
<a href="http://lagua.nl/" target="_blank">http://lagua.nl</a><br></p></div></div>
</div>
</div></blockquote></span></div><br></div></blockquote></div><br><br clear="all"><br>-- <br><div><div><p> 
W.S. Hager<br>
Lagua Web Solutions<br>
<a href="http://lagua.nl/" target="_blank">http://lagua.nl</a><br></p></div></div>
</div>
</div></blockquote></span></div><br></div></blockquote></div><br><br clear="all"><br>-- <br><div class="gmail_signature"><div>
<p> 
W.S. Hager<br>
Lagua Web Solutions<br>
<a href="http://lagua.nl/" target="_blank">http://lagua.nl</a><br></p></div></div>
</div>