Equivalence of expressions up to permutation of variables
Subject: Equivalence of expressions up to permutation of variables
From: Stavros Macrakis
Date: Wed, 27 Jun 2007 11:38:35 -0400
On 6/27/07, Chris Sangwin <sangwinc at for.mat.bham.ac.uk> wrote:
>
> Is there an existing Maxima function which will establish a possible
> substitution of variables [v_i=u_i,... with the property that
>
> subst(v_i=u_i,...,ex_1)=ex_2
No, but there certainly should be for at least the simple cases....
There are different notions of "equality" here including
> (1) that above, based on Maxima's data structure and
> (2) ratsimp(subst(v_i=u_i,...,ex_1)-ex_2)=0.
>
Exactly. This is called unification and there has been a lot of work on
it. When you are looking for simple syntactic substitution (with no
simplifications, equivalences, etc., but with the possibility of having the
same term in multiple places), there is a linear-time algorithm I believe.
Then there are extensions to the associative/commutative case. When you
start having more complicated equivalence functions / simplifications,
things quickly get very hard and soon enough uncomputable, no doubt....
-s