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
