next up previous contents
Next: The Andrews-Curtis Transformation functions Up: The Representation Previous: The inverse function inv   Contents

The pinch function pinch

We need to elide generators which are concatenated to their inverse. So the combinations 'aA', 'Aa', 'bB' and 'Bb' disappear from the string. We stack the first generator in the string and then compare it with the second generator. If the next element is an inverse we pop the generator from the stack. Otherwise, we push the next generator from the string and continue the process.

For words of length 0 or 1 there can be no pinching so we simply return the word.

Note that this operation constructs a new word. An optimization is to make the word process destructive to save space. This is not yet implemented.

(defun pinch (word)
 "given a word pinch out all inverse elements"
 (let ((stack nil) (wlen (- (length word) 1)))
  (if (> wlen 0)
   (progn
    (push (elt word 0) stack)
    (dotimes (i wlen) 
     (cond
      ((and (eq (first stack) #\\a) (eq (elt word (+ i 1)) #\\A)) (pop stack))
      ((and (eq (first stack) #\\A) (eq (elt word (+ i 1)) #\\a)) (pop stack))
      ((and (eq (first stack) #\\b) (eq (elt word (+ i 1)) #\\B)) (pop stack))
      ((and (eq (first stack) #\\B) (eq (elt word (+ i 1)) #\\b)) (pop stack))
      (t (push (elt word (+ i 1)) stack))))
    (concatenate 'string (reverse stack)))
    word)))


root 2004-05-05