
January 29th, 2010, 04:52 AM
#1
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+BC)*(C+C)
(D+D)*(B+AD)
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 NPHard), 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 wellknown problem?
Thank you.

January 29th, 2010, 05:31 AM
#2
Re: Expression equivalence checking
3.
Input:
(A+A)+B
(A+B)+A
Output:
No
do you mean that rearrangements cannot pass over parentheses ?

January 29th, 2010, 06:53 AM
#3
Re: Expression equivalence checking

January 29th, 2010, 08:02 AM
#4
Re: Expression equivalence checking
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 nuple (A is positive if a=+...)
> order the nuples lexicographically
> substitute each nuple element with its order
( example: +BA+AC > {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)+BC > (A)(+)(A)+BC > (A)+(A)+BC > {(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)+AC > ... > {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+BC)*(C+C) >
(A+BC) > {(A),(B)}{(C)}
(C+C) > {(C),(C)}{}
> {{(A),(B)}{(C)},{(C),(C)}{}} > {{1,2}{3},{3,3}{}}
(D+D)*(B+AD) >
(D+D) > {(D),(D)}{}
(B+AD) > {(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...

January 29th, 2010, 12:36 PM
#5
Re: Expression equivalence checking
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+AD) to (B+AD)*(D+D) ? (where is an appropriate rule in your algorithm? )
3. Can you please consider next example.
XYXZ/YZ
PQQR/PR
XYXZ/YZ
X*Y > { {X}{}, {Y}{} }
X*Z > { {X}{}, {Z}{} }
Y*Z > { {Y}{}, {Z}{} }
XYXZ/YZ > { XY }{ XZ/YZ } > { {{X},{Y}} }{ {XZ},{YZ} } > { { {X}{}, {Y}{} } }{ { { {X}{}, {Z}{} } },{ { {Y}{}, {Z}{} } } } > { {{1}{},{2}{}} }{ { { {1}{},{3}{} } }, { { {2}{},{3}{} } } }
PQQR/PR > { {{1}{},{2}{}} }{ { { {2}{},{3}{} } }, { { {1}{},{3}{} } } }
and as you can see these normal forms are not equivalent.

January 30th, 2010, 04:10 AM
#6
Re: Expression equivalence checking
>> 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 XYXZ/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} ).

January 30th, 2010, 07:22 AM
#7
Re: Expression equivalence checking
>>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 NPcomplete 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+BC)*(C+C)
(D+D)*(B+AD)
with
(X+YZ)*(Z+Z)
(A+A)*(X+YZ)
then I'll get:
(X+YZ) > {(X),(Y)}{(Z)}
(Z+Z) > {(Z),(Z)}{}
(X+YZ)*(Z+Z) > { {(X),(Y)}{(Z)} },{ {(Z),(Z)}{} } > { {1,2}{3} },{ {3,3}{} }
(A+A)*(X+YZ) > { {(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

January 30th, 2010, 08:48 AM
#8
Re: Expression equivalence checking
well, if you are sure that the problem is NPcomplete 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 nonequivalent. 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.

January 30th, 2010, 01:26 PM
#9
Re: Expression equivalence checking
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 NPcomplete
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.

January 31st, 2010, 05:44 AM
#10
Re: Expression equivalence checking
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 15 to build it.
in particular, we could think of steps 15 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!
Last edited by superbonzo; January 31st, 2010 at 07:55 AM.

February 1st, 2010, 12:30 PM
#11
Re: Expression equivalence checking
Thank you.
I'll work on your idea.
Last edited by amberovsky; February 2nd, 2010 at 11:11 AM.
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
This is a Codeguru.com survey!
