Expression equivalence checking

Hi All!.

I have a following problem:

It is given two arithmetic expressions, operations - +, -, *, /, (), operands - just standard identifiers.
The question is: whether it is possible to rename identifiers and to rearrange operands at commutative operations (+, *) so that to reduce one expression to another.

For example:
1.
Input:
A+B
C+B
Output:
Yes

2.
Input:
(A+B-C)*(C+C)
(D+D)*(B+A-D)
Output:
Yes

3.
Input:
(A+A)+B
(A+B)+A
Output:
No

I found the (http://escholarship.org/uc/item/58v124c7) "Expression equivalence checking using interval analysis" article, but that algorithm requires defined intervals for identifiers values (and it does not allow the infinity value).
My algorithm is O(n^2) (please note this problem is NP-Hard), and i want to find a more efficient solution.

Does another (standard) algorithm exist for this problem? Or, may be, this problem can be reduced to another well-known problem?

Thank you.

Quote:

---

3.
Input:
(A+A)+B
(A+B)+A
Output:
No

---

do you mean that rearrangements cannot pass over parentheses ?

Yes

usually this kind of problems are solved by translating the expression into a properly defined normal form.
first of all suppose the input has no spaces and it's well formed.
let's use the letter A... for identifier placeholders, a... for operators placeholders, Z... as generic placeholders and z... as generic expression placeholders.
We'll go by structural induction:

Code:

---

1) aAbBcCd... where abc are + or -
        -> split the symbol placeholders in a positive and a negative n-uple (A is positive if a=+...)
        -> order the n-uples lexicographically
        -> substitute each n-uple element with its order
        ( example: +B-A+A-C -> {B,A}{A,C} -> {A,B}{A,C} -> {1,2}{1,3} )

2) AaBbCc... where abc are + or -
        -> +AaBbCc -> the proceed as in 1)

3) z(ZYX...)y
        -> z(Z)(Y)(X)y...
                where (+) -> +, (-) -> - and so on
                and (A),(B),... are treated as new symbols

( examples:
        (A+A)+B-C -> (A)(+)(A)+B-C -> (A)+(A)+B-C -> {(A),(A),B}{C} -> {1,1,2}{3}
        (B+B)-C+A -> (B)(+)(B)-C+A -> (B)+(B)-C+A -> {(B),(B),A}{C} -> {1,1,2}{3}
        (A+B)+A-C -> ... -> {1,2,3}{4}
        )

4) given expressions z*y -> the lexicographically ordered pair of ... well look at the examples
5) given expressions z/y -> the ordered pair  ... again, it's better looking at the examples

examples:

(A+B-C)*(C+C) ->
        (A+B-C) -> {(A),(B)}{(C)}
        (C+C)        -> {(C),(C)}{}
                -> {{(A),(B)}{(C)},{(C),(C)}{}} -> {{1,2}{3},{3,3}{}}

(D+D)*(B+A-D) ->
        (D+D)        ->        {(D),(D)}{}
        (B+A-D)        ->        {(A),(B)}{(D)}
                -> {{{(A),(B)}{(D)}}{(D),(D)}{}} -> {{1,2}{3},{3,3}{}}

Z/A -> {{Z}{},{A}{}} -> {{1}{},{2}{}}

---

so two inputs are equivalent if their normal forms coincide. At frst sight the resulting algorithm should be nlog(n), but I've not payed much attention to details. I hope this give you some ideas to work on...

Thank you, but there is some unclear moments.

1. What a difference between * and / ?
As i understand you use one syntax:
A*B -> { {A}{},{B}{} }
A/B -> { {A}{},{B}{} }

2. A sorting stage is also unclear.
Why did you change (D+D)*(B+A-D) to (B+A-D)*(D+D) ? (where is an appropriate rule in your algorithm? )

3. Can you please consider next example.
XY-XZ/YZ
PQ-QR/PR

XY-XZ/YZ

X*Y -> { {X}{}, {Y}{} }
X*Z -> { {X}{}, {Z}{} }
Y*Z -> { {Y}{}, {Z}{} }

XY-XZ/YZ -> { XY }{ XZ/YZ } -> { {{X},{Y}} }{ {XZ},{YZ} } -> { { {X}{}, {Y}{} } }{ { { {X}{}, {Z}{} } },{ { {Y}{}, {Z}{} } } } -> { {{1}{},{2}{}} }{ { { {1}{},{3}{} } }, { { {2}{},{3}{} } } }

PQ-QR/PR -> { {{1}{},{2}{}} }{ { { {2}{},{3}{} } }, { { {1}{},{3}{} } } }

and as you can see these normal forms are not equivalent.

>> Thank you, but there is some unclear moments.

oh sorry, as I sead in my previous post I didn't payed much attention to details ( you know, often in this kind of forums people read and write post during working days so we often simply give ideas to work on rather then complete solutions ... )

>> 1. What a difference between * and / ?

in the * case the pair is lexicographically ordered, thus {(D),(D)}{} comes after {(A),(B)}{(D)} where the symbol strings "(D)","(A)",etc... are compared

>> 3. Can you please consider next example...

note that I supposed '/' has a higher precedence then '*',

thus XY-XZ/YZ should be written X*Y-(X*Z)/(Y*Z) as you intended it

we have:
X*Y -> { {X}{}, {Y}{} }
X*Z -> { {X}{}, {Z}{} }
Y*Z -> { {Y}{}, {Z}{} }
(X*Z)/(Y*Z) -> {{ {(X)}{}, {(Z)}{} },{ {(Y)}{}, {(Z)}{} }}
X*Y-(X*Z)/(Y*Z) -> {{ {X}{}, {Y}{} }}{{{ {(X)}{}, {(Z)}{} },{ {(Y)}{}, {(Z)}{} }}} ->
{{ {1}{}, {2}{} }}{{{ {3}{}, {4}{} },{ {5}{}, {4}{} }}}

whilst
(Q*R)/(P*R) -> {{ {(Q)}{}, {(R)}{} },{ {(P)}{}, {(R)}{} }}
P*Q-(Q*R)/(P*R) -> {{{P}{},{Q}{}}}{{{ {(Q)}{}, {(R)}{} },{ {(P)}{}, {(R)}{} }}} ->
{{{1}{},{2}{}}}{{{ {3}{}, {4}{} },{ {5}{}, {4}{} }}}


that are equivalent. That sead, I have not formally demonstrated that the algorithm works ... anyway, the idea is to get a normal form by lexicographically ordering symbols of commutative operands and by "enriching" symbols when pass over parentheses ( so "A" -> "(A)" -> "((A))" -> ... ). Finally, each symbol is subsituted with its final order (like {A,B,C,(Z),A,B,(Z)} -> {1,2,3,4,1,2,4} ).

>>oh sorry, as I sead in my previous post I didn't payed much attention to details ( you know, often in this kind of forums people read and write post during working days so we often simply give ideas to work on rather then complete solutions ... )

Yes, I understand, but on the other forum peoples say that this problem is NP-complete and thus can't be solved in the polynomial time.

>> >> 1. What a difference between * and / ?
in the * case the pair is lexicographically ordered, thus {(D),(D)}{} comes after {(A),(B)}{(D)} where the symbol strings "(D)","(A)",etc... are compared

So, expressions A*B and A/B will be the same ?
A*B -> { {A}{},{B}{} }
A/B -> { {A}{},{B}{} }

and if I'll rewrite example
(A+B-C)*(C+C)
(D+D)*(B+A-D)

with
(X+Y-Z)*(Z+Z)
(A+A)*(X+Y-Z)

then I'll get:
(X+Y-Z) -> {(X),(Y)}{(Z)}
(Z+Z) -> {(Z),(Z)}{}
(X+Y-Z)*(Z+Z) -> { {(X),(Y)}{(Z)} },{ {(Z),(Z)}{} } -> { {1,2}{3} },{ {3,3}{} }

(A+A)*(X+Y-Z) -> { {(A),(A)}{} },{ {(X),(Y)}{(A)} } -> { {1,1}{} },{ {2,3}{1} }

wrong?


>> anyway, the idea is to get a normal form by lexicographically ordering symbols of commutative operands and by "enriching" symbols when pass over parentheses ( so "A" -> "(A)" -> "((A))" -> ... ). Finally, each symbol is subsituted with its final order (like {A,B,C,(Z),A,B,(Z)} -> {1,2,3,4,1,2,4} ).

Let's consider following example:

P+(P+Z) -> { P, (P), (Z) }{} -> { 1, 2, 3}{}
P+(X+Z) -> { P, (X), (Z) }{} -> { 1, 2, 3}{}


wrong?

p.s. I will be improbably happy, if this problem can be solved throught your way :)

well, if you are sure that the problem is NP-complete then we are sure that my algorithm sketch won't work :)
Are you sure that the problem to which those people referred is exactly the one you describe ?
I ask because your notion of "equivalence" of expressions is stronger then the intuitive notion of arithmetic equivalence; for example, you assume a+(b+b) and b+(a+b) or a(b+c) and ab+ac to be non-equivalent. This "strongness" could make the problem solvable in polynomial time.

>>..wrong?

those are good counterexamples...

now, certainly I could add new rules in order to make those examples work. The problem is that we could go on indefinitely (and I do not have indefinite time :) ). You should tackle the problem formally and rigorously define by structural induction the input forms and their equivalence condition in order to give a formal proof of (non)NP completeness.

Dear superbonzo, please be sure that I have been spending a lot of time on this problem =)

Unfortunately I'm not a guru and I don't have much skills to prove NP-complete :(

Your idea is to
1) creating a set of characteristics which can describe an expression by unique way
2) sorting (sub)expression using those characeristics and obtaining a "normal" form
3) syntax checking for an equivalence

You created 3 (2 exactly) characteristics:
1. lexicographically order
2. ordering by operations +,-*,/
3. you use identifiers "depth" - creating new identifier on each ().

I suppose you improved last by adding a reference to the "parent" identifier, e.g.
A+(A+B) -> { A, (A), (B)}{} -> {1, 2.1, 3}{}

but it doesn't work in case
C+G+(A+C) -> {1, 2, 3, 4.1}{}
B+C+(A+C) -> {1, 2, 3, 4.2}{}

so, it seems that lexicographical ordering won't help us...

I worked in similar way, I did not use {}-scheme, I just sorted expressions depending on (like yours) characteristics.

So,
1. I would like to read any solutions on similar problems. Please refer me if you know such solutions
2. What are your rules to make those examples work?
3. I can add a lot of characteristics. Is it possible to prove that they are enough?

Thank you.

As I sead before you must tackle the problem formally:

first of all let's get rid of minuses: given that you're not allowed manipualting signs ( A -> -(-A), and so on) we simply define two sets of symbols {A,B,C,...} and {Z,Y,X,...} of "positive" and "negative" symbols, respectively. Equivalence of expression will not allow swapping symbols of different "sign" (so, the inputs A and Z are not equivalent ).

then

1- "A","B",...,"Z" are expressions, called "symbols"
2- "(e)" is an expression whenever "e" is an expression
3- "e1+e2+..+en" ,n>=2 is an expression whenever "ej" is an expression for every j
4- "f1*f2*...*fk" ,k>=2 is an expression whenever for every j "fj" has the form "X" and X is a symbol or it has the form "(e)" and e is an expression
5- "f1/f2" is an expression whenever for every j "fj" has the form "X" and X is a symbol or it has the form "(e)" and e is an expression

in general, we say that an input form is a well formed expression iff there exists a unique sequence of steps 1-5 to build it.

in particular, we could think of steps 1-5 as functions:

1: capital letter -> the associated expression
2: expression e -> (e)
3: expression e1,...,en, n>=2 -> e1+...+en
...and so on

for example

A*(B+C)*(D) -> 4(1(A),2(3(1(B),1(C))),2(1(D)))

we will call the right hand side the "structure tree" S(e) of the input expression e.

finally, two inputs are equivalent if one can be cast into the other by the application of the following transformations to their structure trees:

I) a permutation of the set of positive symbols
II) a permutation of the set of negative symbols
III) a permutation of the arguments of function 3
IV) a permutation of the arguments of function 4

conditions III) and IV) are equivalent to asking if the labeled trees S(e1) and S(e2) are isomorphic; google for tree isomorphism or tree canonicalization problems, as far as I can remember its solution is logtime.
Given finite sets of positive and negative symbols this makes the whole algorithm logtime. Bye!

Thank you.

I'll work on your idea.