  This paper, following (Dymetman:1998), presents an approach to grammar
description and processing based on the geometry of cancellation diagrams, a
concept which plays a central role in combinatorial group theory
(Lyndon-Schuppe:1977). The focus here is on the geometric intuitions and on
relating group-theoretical diagrams to the traditional charts associated with
context-free grammars and type-0 rewriting systems. The paper is structured as
follows. We begin in Section 1 by analyzing charts in terms of constructs
called cells, which are a geometrical counterpart to rules. Then we move in
Section 2 to a presentation of cancellation diagrams and show how they can be
used computationally. In Section 3 we give a formal algebraic presentation of
the concept of group computation structure, which is based on the standard
notions of free group and conjugacy. We then relate in Section 4 the geometric
and the algebraic views of computation by using the fundamental theorem of
combinatorial group theory (Rotman:1994). In Section 5 we study in more detail
the relationship between the two views on the basis of a simple grammar stated
as a group computation structure. In section 6 we extend this grammar to handle
non-local constructs such as relative pronouns and quantifiers. We conclude in
Section 7 with some brief notes on the differences between normal submonoids
and normal subgroups, group computation versus rewriting systems, and the use
of group morphisms to study the computational complexity of parsing and
generation.
