Sat Aug 14 14:25:38 CEST 2010

Binary Tree Permutations

( Of relevance to understanding PF's memory model [1]. )

I'm trying to understand the group of binary tree permutations.  Let's
start with these two, intuitively basic operations:

   * swap:        a b  S  =  b a
   * rotate:  a (b c)  L  =  (a b) c
              (a b) c  R  =  a (b c)

Notation: Lower case letters or digits indicate trees, upper case
letters are tree transformations.  Group action of transformation T on
tree t is denoted as tT.  Binary trees have only one non-associative
operator: (t1 t2) is the tree made from splicing together the subtrees
t1 and t2.  The relation t1 -T-> t2 is shorthand for t1 T = t2.

Questions: 1) is this set minimal? and 2) does it generate all
permutations of binary trees?

For convenience, let's stick to permutations of infinite trees, but
have them go only finitely deep.  This means the group of
transformations is infinite in size but more "regular" than a
transformation group of finite-size trees as there are no special
border conditions.

The answer to 1) is no.  It is possible to write L = SRSRS.  Proof:

    a (b c)  -S->  (b c) a
             -R->  b (c a)
             -S->  (c a) b
             -R->  c (a b)
             -S->  (a b) c

We also can't write S in terms of L and R because both L and R leave
invariant the ordering of the leaf nodes, while S does not.

To understand more about 2) let's see what the relation is to lists.

Suppose that a binary tree can be transformed to a (left or right
leaning) list by a succession of L and R operations.  The inverse is
then also true: any list can be transformed back into an arbitrary
binary tree with the same leaf-node order using a particular
combination of L and R transformations.

So is the premise true?  Or do we need another operation?

From inspection, it seems that rotating a tree to a (right leaning)
list can be done by R operations on _subtrees_.  The question is then:
how to express R operations on subtrees?

I.e. how to express:  a ((b c) d) -> a (b (c d))

More generally, how to take a tree transformation T and re-root it at
a different base node?

Intuitively this seems to be a new operation as you "swipe something
under the carpet".

Let's try: if the basic operations of S,L,R can be constructed to
operate only on the right (or left) node of the tree, expressed in
terms of root-node S,L,R operations, then we can recursively transform
any operation.

    r (a b) -S1-> r (b a)

But I don't immediately see how to construct S1.  My first attempt brought
me to some other primitives: 3-element right-leaning rotations LS and
SR, which are each other's inverse:

    1 (2 3) -L-> (1 2) 3
            -S-> 3 (1 2)

    3 (1 2) -S-> (1 2) 3
            -R-> 1 (2 3)

The left-leaning variants are RS amd SL.

    (1 2) 3 -R-> 1 (2 3)
            -S-> (2 3) 1

    (2 3) 1 -S-> 1 (2 3)
            -L-> (1 2) 3

Because they are embeddings of 3-element list rotations we have:

    (ST)^3 = (TS)^3 = I where T is L,R.

From these basic operations I can't see how to implement the re-rooted
swap operation:

    1 (2 3) -> 1 (3 2),

which seems to be a genuine primitive transformation.

This reminds me of the hint at necessity of '>R' and 'R>' or 'dip'
when writing Forth or Joy code: you need a second stack to hide
intermediate results.  (Additionally you need a "free" stack to
implement creation and destruction of cells in a conservative way.)

Then the question might be: if we replace S, R, L by S', R', L' all
rooted at the right subtree, what can we generate?

   * swap':        r (a b)  S'  =  r (b a)
   * rotate':  r (a (b c))  L'  =  r ((a b) c)
               r ((a b) c)  R'  =  r (a (b c))
For sure, the group these generate is isomorphic to the other one, but
it's not a complete set as it leaves the whole left subtree invariant.

Here 'r' really resembles the Forth return stack.  The '>R' and 'R>'
operations could be

    r (a b)  -L->  (r a) b
    (r a) b  -R->  r (a b)
( However, in the s-expression encoding of Forth I would use the
version which builds stacks as right-leaning trees. )

Again the questions: 1) minimal set?  2) all permutations?

Approach: My hunch is that it's not necessary to provide an infinite
set of primitives: I think you can build level 2 from the connection
between 0 and 1.  Then when that works, do we have all?


Antti[4] points out I'm looking for Thompson's group[2].  Follow
through on [3].

[1] entry://../libprim/20100814-114746
[2] http://en.wikipedia.org/wiki/Thompson_groups
[3] http://www.math.binghamton.edu/matt/thompson/cfp.pdf
[4] http://ndirty.cute.fi/~karttu/matikka/stebrota.htm