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

[Pavel Velikhov]

Trees won’t help much here. The difficulty with path expression is due to the // step, which adds non-determinism.

//w/x subsumes /w/x/y/z/w/x
//w/w doesn’t subsume /w/x/w

Regular languages also have determinism and all the algorithms for them are exceptionally well-studied.
Or you can do an algorithm with backtracking, but it could get hairy.


> On 29 Jan 2016, at 20:53, W.S. Hager <wshager at gmail.com> wrote:
> 
> This is the best I (actually Google) can do.
> 
> Proof:
> https://coq.inria.fr/library/Coq.MSets.MSetGenTree.html <https://coq.inria.fr/library/Coq.MSets.MSetGenTree.html>
> Test:
> 
> http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-of-another-binary-tree/ <http://www.geeksforgeeks.org/check-if-a-binary-tree-is-subtree-of-another-binary-tree/>
> At some point I'll look into this myself, it's a nice challenge.
> 
> 
> donderdag 28 januari 2016 heeft Pavel Velikhov <pavel.velikhov at gmail.com <>> het volgende geschreven:
> 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.
> 
> 
> -- 
> W.S. Hager
> Lagua Web Solutions
> http://lagua.nl <http://lagua.nl/>
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://x-query.com/pipermail/talk/attachments/20160130/55b8f6f9/attachment.html>