Am 27.11.2014 um 16:47 schrieb Matthew Rocklin:
- Is there need for nonlinear patterns? I plan to account for them, but
they make the algorithm a bit more complicated. Nonlinear, AC pattern
matching is NP complete. Linear AC pattern matches can be found in
polynomial time.
I haven't thought much about this. Is X*X.T non-linear?
From other mentions of "linear" and "nonlinear", I infer that patterns
with multiple occurrences of the same symbol are always nonlinear.
Might have to do with the fact that to check whether such a pattern
matches, you have to traverse the entire subtrees that you'd want to
match with X and see whether the subtrees are the same.
IIRC from my university time, matching nonlinear patterns like the above
is one of the key ingredients that makes a Prolog interpreter
Turing-complete.
--
You received this message because you are subscribed to the Google Groups
"sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sympy.
To view this discussion on the web visit
https://groups.google.com/d/msgid/sympy/54776956.9080409%40durchholz.org.
For more options, visit https://groups.google.com/d/optout.
