# Why doesn't FullSimplify find simpler expression given a set of transformation rules?

I've defined a set of rules, which I want to use with FullSimplify, as follows:

transf1[expr_] := expr /. (a_⊕b_)⊕c_ -> a⊕(b⊕c)
transf2[expr_] := expr /. a_⊕b_ -> b⊕a
transf3[expr_] := expr /. a_⊕-a_ -> 0
transf4[expr_] := expr /. a_⊕0 -> a
transf5[expr_] := expr /. a_⊖b_ -> a⊕-b


But when I try to actually use them, I get no result:

FullSimplify[x⊕y⊖x,TransformationFunctions->{transf1,transf2,transf3,transf4,transf5}]


x⊕(y⊖x)

At the same time, there does exist a sequence of transformations, which does yield a simpler result:

transf4@transf3[transf2 /@ transf1@transf2@transf5[x⊕y⊖x]]


y

Am I using FullSimplify wrongly? Isn't the above the correct way to provide custom transformation functions?

• FullSimplify won't evaluate all possible compositions.... perhaps a modified ComplexityFunction is necessary to guide it through a good path Feb 29 '16 at 21:00
• See 69262 and 96633. Feb 29 '16 at 21:25

Here is a analysis of the problem which doesn't give a solution :

You can follow what FullSimplifyis doing with this modified code :

transf1[expr_] := (Print[1, " ", expr, " "];expr /. (a_⊕b_)⊕c_ -> a⊕(b⊕c))
transf2[expr_] := (Print[2, " ", expr, " "];expr /. a_⊕b_ -> b⊕a)
transf3[expr_] := (Print[3, " ", expr, " "];expr /. a_⊕-a_ -> 0)
transf4[expr_] := (Print[4, " ", expr, " "];expr /. a_⊕0 -> a)
transf5[expr_] := (Print[5, " ", expr, " "];expr /. a_⊖b_ -> a⊕-b)

FullSimplify[x\[CirclePlus]y\[CircleMinus]x,
TransformationFunctions -> {transf1, transf2, transf3, transf4,
transf5}]


You see that the transformation N°5 is tried first. It should give x+(y+(-x)), but you see nowhere this expression in the following lines. I presume therefore that the transformation N°5 is not used. There is a explanation for that : The ComplexityFunction, which is similar to LeafCount is worse with x+(y+(-x)) than with x+(y-x).

The problem is that one can hardly find a ComplexityFunction that get better trough the sequence that gives the solution :

• Does FullSimplify require that ComplexityFunction monotonically decreases on each transformation? Mar 1 '16 at 5:29
• @Ruslan Excellent question, but I don't know the answer. Maybe the answer can be deducted from here ? All the possibilities form a tree of possibilities. I don't know how FullSimplifygo through the tree. I don't even know what is the "current state" that memorize what has already been tried (it could be something like a list of candidates expressions to further optimize) Mar 1 '16 at 7:40
• @Rusian I fact, I was very surprised to see how basic is the bevavior of FullSimpllify in your very interesting example (where the expressions are inert) Mar 1 '16 at 7:47

Instead of defining transformation rules you can try to achieve the same by defining your operations:

CircleMinus[a_, b_] := CirclePlus[a, -b]
CirclePlus[a_, 0] := a
CirclePlus[a_, b_] := If[a == -b, 0]
SetAttributes[CirclePlus, {Orderless, Flat}]


and using a simple Simplify

Simplify[CirclePlus[x, CircleMinus[y, x]], Assuming[x != 0, y != 0]]
(* 0 *)


Correction

Indeed, there were problems with my solution. Now they are corrected:

ClearAll[CirclePlus, CircleMinus]
CircleMinus[a_, b_] := CirclePlus[a, -b]
CirclePlus[a_, 0] := a
CirclePlus[a_] := a
CirclePlus[AA___, a_, BB___, b_, CC___] := CirclePlus[AA, BB, CC] /; a === -b
SetAttributes[CirclePlus, {Orderless, Flat}]

CirclePlus[x, CircleMinus[y, x]]
(* y *)

• The problem here is that this way some transformations will be applied unconditionally, even without Simplify. And in your use of Simplify the assumption is not even used — it works without it (it's in fact unneeded at all, since nothing will change if x==0||y==0). Mar 1 '16 at 5:28