Re: subtree isomorphism problem
- From: "Matt Timmermans" <mt0000@xxxxxxxxxxxxxxxxxxxxxxxxxx>
- Date: Wed, 9 Nov 2005 21:06:01 -0500
Yes, I had the wrong problem in mind. Your problem is hard.
You can look at references like this:
but if this is really for an ad-hoc query system, you'll want to simplify
For example, if you have a query a(b(c),b(d)) and a text a(b(c,d)), would
you expect to find a match or not? If you're really looking for subtree
isomorphism, then the answer is "no", but if you say "yes" then your problem
becomes much simpler, and can be solved easily during a postorder traversal
of the text tree.