1.1.1 Double Stack Construction

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
branch * (0,I)
hold *
go forward down the branch as dictated by the finite state machine
branch * (0,I)
hold * (4,1) (3,1) (2,1) (1,1)
serve a waiting customer off the hold stack producing "1"
branch * (0,I) (1,I*1)
hold * (4,1) (3,1) (2,1)
go forward down the branch
branch * (0,I) (1,I*1)
hold * (4,1) (3,1) (2,1) (4,2) (2,2) (1,2)
serve a waiting customer off the hold stack producing "11"
branch * (0,I) (1,I*1) (1,I*1*1)
hold * (4,1) (3,1) (2,1) (4,2) (2,2)
since we are at depth 2 we don't go forward down the branch but serve an holding number producing "12"
branch * (0,I) (1,I*1) (2,I*1*2)
hold * (4,1) (3,1) (2,1) (4,2)
since we are at depth 2 we don't go forward down the branch but serve an holding number producing "14"
branch * (0,I) (1,I*1) (4,I*1*4)
hold * (4,1) (3,1) (2,1)
since we are at depth 2 we don't go forward down the branch but serve an holding number producing "2"
branch * (0,I) (2,I*2)
hold * (4,1) (3,1)
etc.

 home Contents