>>>> Let m = p:q, n = r:s with p, q, r, s != NIL be valid moves with m != ID >>>> and >>>> n != ID. Then the following reduction and commutation rules apply: >>>> >>>> 1. p!~ r: m * n = n * m >>>> 2. p< r: illegal (since this implies q<= r which implies p ~ q and >>>> thus m invalid) >>>> 3. p = r: illegal (since this implies q<= r which implies p ~ q and >>>> this m invalid) >>>> 4. p> r: does not commute if q< s. Otherwise m * n = n * [r -> s]m >>>> 5. p!~ s: m * n = n * m >>>> 6. p< s: illegal (since this implies p ~ q and thus m invalid) >>>> 7. p = s: does not commute >>>> 8. p> s: illegal (since p> s implies there is an s already which >>>> will conflict with r:s) >>>> 9. q!~ r: m * n = n * m >>>> 10. q< r: m * n = [q -> p]n * m >>>> 11. q = r: m * n = p:s (transitivity of moves) >>>> 12. q> r: m * n = n * [r -> s]m >>>> 13. q!~ s: m * n = n * m >>>> 14. q< s: does not commute if p> r. Otherwise m * n = [q -> p]n * m >>>> 15. q = s: illegal (since s conflicts with r:s) >>>> 16. q> s: illegal (since s conflicts with r:s) >>>> >>>> Allowing add node and remove node operations the following additional >>>> conditions apply: >>>> >>>> Let m = p:q, n = r:s be valid moves with m != ID and n != ID. Then the >>>> reduction and commutations rules 1. to 16. apply with extra conditions on >>>> 4., 10., 12. and 14.: >>>> >>>> 4'. if s = NIL and q = NIL then m * n = -r. Otherwise if s = NIL then >>>> m, n do not commute. >>>> 10'. illegal if p = NIL >>>> 12'. if s = NIL then m * n = -r * -p >>>> 14'. illegal if p = NIL >>> >> >>> could you please provide a simple example? >> Here are simple examples for each of the above cases and its respective special cases. Note that I refined 14'. to 14'. if p = NIL: does not commute if the parent of s is q. Illegal otherwise 1. >/a:/b >/c:/d = >/c:/d >/a:b 2. >/a:/b >/a/b:/c illegal 3. >/a:/b >/a:/c illegal 4. >/a/b:/c >/a:/d = >/a:/d >/d/b:/c 4. >/a/b:/c >/a:/c/d does not commute (q < s) 4'. -/a/b -/a = -/a (s = NIL and q = NIL) 4'. >/a/b:/c -/a = does not commute (s = NIL) 5. >/a:/b >/c:/d = >/c:/d >/a:b 6. >/a:/b >/c:/a/d illegal 7. >/a:/b >/c:/a does not commute 8. >/a/d:/b >/c:/a illegal 9. >/a:/b >/c:/d = >/c:/d >/a:b 10. >/a:/b >/b/c:/d = >/a/c:/d >/a:/b 10'. +/b:{} >/b/c:/ illegal 11. >/a:/b >/b:/c = >/a:/c 12. >/a:/b/c >/b:/d = >/b:/d >/a:/d/c 12'. >/a:/b/c -/b = -/b -/a 13: >/a:/b >/c:/d = >/c:/d >/a:b 14. >/a:/b >/c:/b/d = >/c:/a/d >/a:/b 14. >/a/b:/b >/a:/b/d does not commute (p > r) 14'. +/b:{} >/c:/b/c does not commute (parent of s = q and p = NIL) 14'. +/b:{} >/c:/b/c/d illegal (p = NIL) 15. >/a:/b >/c:/b illegal 16. >/a:/b/d >/c:/b illegal Have fun ;-) Michael