<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="">Trees won’t help much here. The difficulty with path expression is due to the // step, which adds non-determinism.<div class=""><br class=""></div><div class="">//w/x subsumes /w/x/y/z/w/x</div><div class="">//w/w doesn’t subsume /w/x/w</div><div class=""><br class=""></div><div class="">Regular languages also have determinism and all the algorithms for them are exceptionally well-studied.</div><div class="">Or you can do an algorithm with backtracking, but it could get hairy.</div><div class=""><br class=""></div><div class=""><br class=""><div class=""><div><blockquote type="cite" class=""><div class="">On 29 Jan 2016, at 20:53, W.S. Hager <<a href="mailto:wshager@gmail.com" class="">wshager@gmail.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class="">This is the best I (actually Google) can do.<div class=""><br class=""><div class="">Proof:<br class=""><a href="https://coq.inria.fr/library/Coq.MSets.MSetGenTree.html" target="_blank" class="">https://coq.inria.fr/library/Coq.MSets.MSetGenTree.html</a><div class=""><p dir="ltr" class="">Test:</p><p dir="ltr" class=""><a href="http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-of-another-binary-tree/" target="_blank" class="">http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-of-another-binary-tree/</a></p><p dir="ltr" class="">At some point I'll look into this myself, it's a nice challenge.</p></div><div class=""><br class=""></div><div class="">donderdag 28 januari 2016 heeft Pavel Velikhov <<a class="">pavel.velikhov@gmail.com</a>> het volgende geschreven:</div><div class=""><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto" style="word-wrap:break-word" class="">Hmm.. testing subsumption is not as trivial as I thought. Here's a cleaner way to do it: represent both path expressions as DFAs and then test subsumption. You'll get DFAs A and B and then test if minimized(B-A) is empty.</div>
</blockquote></div>
</div></div><br class=""><br class="">-- <br 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><br class="">
</div></blockquote></div><br class=""></div></div></body></html>