| Up: 1.1 Klein | ||
|
|
|
|
I think that the best way to explain what the double stack constructions is
to show how it works in this specific example--unfortunately this means I
have to go through a lot of ground work.
Consider two generators of a free-group 1 and 2 and say their inverses are 3 and 4. Now, we want to generate all the words in the group (combinations of 1-4 that do not have 1's besides 3's or 2's besides 4's--they would cancel each other) whose length is N or less. So a simple case would be for N equals 2-- 1, 11, 12, 14, 2, 21, 22, 23, 3, 32, 33, 34, 4, 41, 43, 44. A nice way to make all of the words is to use a finite state machine. The finite state machine would look like the diagram--0 is the initial state of the machine.
Since the generators of this group ends up to be a mobius transformation we
don't want to have to recalculate anything that we have already done. For
instance, if we have already calculated 12222 we don't want to start again to
calculate 122222 or 122223. So we have 2 stacks: one called "hold" and another
called "branch".
The branch stack contains a path to the current position on the tree. Each path marker contains a group member and the state. The hold stack holds the branches that are on hold (luckily numbers don't get too upset by being put on hold--this will be a last in first out so the first number in has to wait a long time). The hold stack only contains a depth and a state--a number between 1 and 4. The depth indicates where on the branch it's waiting to be put.
The following is an example of the double stack running with N, the maximum length of word, set at 2. Here the format is (state, length or depth).
initially the stacks look like this--I means the identity
|
|
| home | Contents |