>>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