Equivalence of expressions up to permutation of variables
Subject: Equivalence of expressions up to permutation of variables
From: Chris Sangwin
Date: Wed, 27 Jun 2007 16:47:30 +0100 (BST)
Richard, Stavros,
Thank you for your helpful comments. I'm glad I didn't simply "blunder
ahead" without consulting first. I shall give this some more thought.
Chris
On Wed, 27 Jun 2007, Stavros Macrakis wrote:
> 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
>