Re: subtree isomorphism problem



Yes, I had the wrong problem in mind. Your problem is hard.

You can look at references like this:

http://citeseer.ist.psu.edu/666894.html

but if this is really for an ad-hoc query system, you'll want to simplify
your requirements.

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.

--
Matt


.