[<<][math][>>][..]Sat Aug 14 14:25:38 CEST 2010

( 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

[Reply][About]

[<<][math][>>][..]