Sunday, August 29, 2010

Undip codewords as lattice walks

Any undip word can be identified with a 2D lattice walk where the allowed steps are N, S, E, W, the walk begins and ends at the origin (such a lattice walk is called a loop), and the walk is furthermore confined to the first quadrant (quarter plane).

Identify 'u' with an North step, and 'd' with an South step (mnemonically 'up' and 'down'). Similarly identify 'n' with an East step and 'p' with a West step.

The "balanced parentheses" rules for undip words (where |x| denotes the number of occurences of the letter 'x') are:

|u| = |d|

|n| = |p| ,

These rules guarantee that total South steps equal total North steps, and total West steps equal total East steps; thus, if a codeword-designated walk begins at the origin, it will end at the origin.

The "nested parentheses" rules guarantee that the walk stays in the first quadrant. The rules are:

|u| >= |d|

|n| >= |p|

for any predicate of an undip word.

In other words, at no point in the spelling of an undip word will there have been more d's than u's, or more p's than n's. On the lattice this means that the walk can never go south or west of the origin-- it is confined to the NorthEast quadrant.

No comments: