Group Theory and Computational Linguistics.
There is currently much interest in bringing together the tradition of categorial grammar, and especially the Lambek calculus, with the recent paradigm of linear logic to which it has strong ties. One active research area is designing non-commutative versions of linear logic (Abrusci, 1995; Retor, 1993) which can be sensitive to word order while retaining the hypothetical reasoning capabilities of standard (commutative) linear logic (Dalrymple et al., 1995). Some connections between the Lambek calculus and computations in groups have long been known (van Benthem, 1986) but no serious attempt has been made to base a theory of linguistic processing solely on group structure. This paper presents such a model, and demonstrates the connection between linguistic processing and the classical algebraic notions of non-commutative free group, conjugacy, and group presentations. A grammar in this model, or G-grammar is a collection of lexical expressions which are products of logical forms, phonological forms, and inverses of those. Phrasal descriptions are obtained by forming products of lexical expressions and by cancelling contiguous elements which are inverses of each other. A G-grammar provides a symmetrical specification of the relation between a logical form and a phonological string that is neutral between parsing and generation modes. We show how the G-grammar can be oriented for each of the modes by reformulating the lexical expressions as rewriting rules adapted to parsing or generation, which then have strong decidability properties (inherent reversibility). We give examples showing the value of conjugacy for handling long-distance movement and quantifier scoping both in parsing and generation. The paper argues that by moving from the free monoid over a vocabulary V (standard in formal language theory) to the free group over V, deep affinities between linguistic phenomena and classical algebra come to the surface, and that the consequences of tapping the mathematical connections thus established can be considerable.
Introduction
There is currently much interest in bringing together the tradition of categorial
grammar, and especially the Lambek calculus [10], with the more recent
paradigm of linear logic [8] to which it has strong ties. One active research area
concerns the design of non-commutative versions of linear logic [1, 14] which
can be sensitive to word order while retaining the hypothetical reasoning capabilities
of standard (commutative) linear logic that make it so well-adapted to
handling such phenomena as quantifier scoping [4].
Some connections between the Lambek calculus and group structure have
long been known [16], and linear logic itself has some aspects strongly reminiscent
of groups (the producer/consumer duality of a formula A with its linear
negation A ? ), but no serious attempt has been made so far to base a theory of
linguistic description solely on group structure.
This paper presents such a model, G-grammars (for "group grammars"),
and argues that:
ffl The standard group-theoretic notion of conjugacy, which is central in G-
grammars, is well-suited to a uniform description of commutative and
non-commutative aspects of language.
ffl The use of conjugacy provides an elegant approach to long-distance dependency
and scoping phenomena, both in parsing and in generation.
ffl G-grammars give a symmetrical account of the semantics-phonology rela-
tion, from which it is possible to extract, via simple group calculations,
rewriting systems with strong decidability properties computing this relation
for the parsing and generation modes.
The paper is organized as follows. In Section 2 we introduce a "group com-
putation" model, using standard algebraic tools such as free groups, conjugacy
and normal subsets. The main deviation from traditional mathematical practice
is in the focus given to the notions of compatible preorder and normal submonoid,
whereas those of compatible equivalence relation and normal subgroup are more
usual in algebra. Section 3 applies this model to linguistic description, and
presents a G-grammar for a fragment of English involving quantification and
relative pronouns. Sections 4 and 5 are concerned with generation and parsing,
which correspond to two ways of exploiting the relation of preorder associated
with the G-grammar, one (generation) in which logical forms are iteratively
rewritten as combinations of logical forms and phonological forms until only
phonological forms are left, the other (parsing) in which phonological forms
are rewritten as combinations of logical forms and inverses of those until, after
cancellation of adjacent inverses, exactly one logical form is left. Section
6 introduces the concept of diagrams, which provide an intuitive and powerful
geometrical representation for G-grammars. These diagrams originate in the
work of Van Kampen [17], and have found applications in combinatorial group
theory and in studies of decidable subclasses of the word problem for groups [11].
They have also been used to produce complete term rewriting specifications for
certain classes of groups [2]. Section 7 discusses in detail the conditions under
which G-grammars and the associated rewriting systems lead to equivalent
definitions of the semantics-phonology relation. These results are used for comparing
G-grammars, context-free grammars, DCG's and categorial grammars.
The section also provides a short discussion of the advantages of G-grammars
for describing in a uniform way commutative and non-commutative aspects of
language. Section 8 applies certain group morphisms to show some strong computability
properties of G-grammars, both for parsing and for generation.
Computation
monoid M is a set M together with a product M \Theta M !M , written
ab, such that:
ffl This product is associative;
ffl There is an element 1 2 M (the neutral element) with a for all
A group is a monoid in which every element a has an inverse a \Gamma1 such that
a
A preorder on a set is a reflexive and transitive relation on this set. When
the relation is also symmetrical, that is, R(x; y) ) R(y; x), then the preorder is
called an equivalence relation. When it is antisymmetrical, that is that is,
y, it is called a partial order.
A preorder R on a group G will be said to be compatible with the group
product iff, whenever R(x; y) and R(x
2.1 Normal submonoids of a group.
We consider a compatible preorder notated x ! y on a group G. The following
properties, for any x; y 2 G, are immediate:
G:
Two elements in a group G are said to be conjugate if there exists y 2 G
such that x . The fourth property above says that the set M of
elements G such that x ! 1 is a set which contains along with an element
all its conjugates, that is, a normal subset of G. As M is clearly a submonoid
of G, it will be called a normal submonoid of G.
Conversely, it is easy to show that with any normal submonoid M of G one
can associate a preorder compatible with G. Indeed let's define x ! y as xy
M . The relation ! is clearly reflexive and transitive, hence is a preorder. It
is also compatible with G, for if x
are in M ; hence x
\Gamma1 is in M ,
implying that x 1 that is, that the preorder is compatible.
Remark. In general M is not a subgroup of G. It is iff x ! y implies y ! x,
that is, if the compatible preorder ! is an equivalence relation (and, therefore,
a congruence) on G. When this is the case, M is a normal subgroup of
G. This notion plays a pivotal role in classical algebra. Its generalization to
submonoids of G is basic for the algebraic theory of computation presented here.
If S is a subset of G, the intersection of all normal submonoids of G containing
S (resp. of all subgroups of G containing S) is a normal submonoid of G
(resp. a normal subgroup of G) and is called the normal submonoid closure
NM(S) of S in G (resp. the normal subgroup closure NG(S) of S in G).
2.2 The free group over V.
We now consider an arbitrary set V , called the vocabulary, and we form the
so-called set of atoms on V , which is notated and is obtained by
taking both elements v in V and the formal inverses v \Gamma1 of these elements.
We now consider the set F (V ) consisting of the empty string, notated 1, and
of strings of the form x 1 x 2 :::x n , where x i is an atom on V . It is assumed that
such a string is reduced, that is, never contains two consecutive atoms which
are inverse of each other: no substring vv \Gamma1 or v \Gamma1 v is allowed to appear in a
reduced string.
When ff and fi are two reduced strings, their concatenation fffi can be reduced
by eliminating all substrings of the form vv \Gamma1 or v \Gamma1 v. It can be proven
that the reduced string fl obtained in this way is independent of the order of
such eliminations. In this way, a product on F (V ) is defined, and it is easily
shown that F (V ) becomes a (non-commutative) group, called the free group
2.3 Group computation
We will say that an ordered pair is a group computation
structure if:
1. V is a set, called the vocabulary, or the set of generators
2. R is a subset of F (V ), called the lexicon, or the set of relators. 1
1 For readers familiar with group theory, this terminology will evoke the classical notion of
group presentation through generators and relators. The main difference with our definition
is that, in the classical case, the set of relators is taken to be symmetrical, that is, to contain
contains r. When this additional assumption is made, our preorder becomes an
equivalence relation.
The submonoid closure NM(R) of R in F (V ) is called the result
monoid of the group computation structure GCS. The elements of NM(R)
will be called computation results, or simply results.
If r is a relator, and if ff is an arbitrary element of F (V ), then ffrff \Gamma1 will be
called a quasi-relator of the group computation structure. It is easily seen
that the set RN of quasi-relators is equal to the normal subset closure of R in
F (V ), and that NM(RN ) is equal to NM(R).
A computation relative to GCS is a finite sequence
quasi-relators. The product r 1 evidently a result, and is called
the result of the computation c. It can be shown that the result monoid
is entirely covered in this way: each result is the result of some computation. A
computation can thus be seen as a "witness", or as a "proof", of the fact that
a given element of F (V ) is a result of the computation structure. 2
For specific computation tasks, one focusses on results of a certain sort, for
instance results which express a relationship of input-output, where input and
output are assumed to belong to certain object types. For example, in computational
linguistics, one is often interested in results which express a relationship
between a fixed semantic input and a possible textual output (generation mode)
or conversely in results which express a relationship between a fixed textual input
and a possible semantic output (parsing mode).
is a group computation structure, and if A is a given subset
of F (V ), then we will call the pair GCSA = (GCS;A) a group computation
structure with acceptors. We will say that A is the set of acceptors, or
the public interface, of GCSA. A result of GCS which belongs to the public
interface will be called a public result of GCSA.
G-Grammars
We will now show how the formal concepts introduced above can be applied to
the problems of grammatical description and computation. We start by introducing
a grammar, which we will call a G-Grammar (for "Group Grammar"),
for a fragment of English (see Fig. 1).
A G-grammar is a group computation structure with acceptors over a vocabulary
log [V phon consisting of a set of logical forms V log and a disjoint set
of phonological elements (in the example, words) V phon . Examples of phonological
elements are john, saw, every, examples of logical forms j, s(j,l),
these logical forms can be glossed respectively as
"john", "john saw louise" and "for every man x, for some woman y, x saw y".
The grammar lexicon, or set of relators, R is given as a list of "lexical
schemes". An example is given in Fig. 1. Each line is a lexical scheme and
represents a set of relators in F (V ). The first line is a ground scheme, which
corresponds to the single relator j john \Gamma1 , and so are the next four lines. The
sixth line is a non-ground scheme, which corresponds to an infinite set of relators,
2 The analogy with the view in constructive logics is clear. There what we call a result is
called a formula or a type, and what we call a computation is called a proof.
l louise
man
A
A

Figure

1: A G-grammar for a fragment of English
obtained by instanciating the term meta-variable A (notated in uppercase) to a
logical form. So are the remaining lines. We use Greek letters for expression
meta-variables such as ff, which can be replaced by an arbitrary expression of
F (V ); thus, whereas the term meta-variables A, B, ., range over logical forms,
the expression meta-variables ff, fi, ., range over products of logical forms and
phonological elements (or their inverses) in F (V ). 3
The notation P[x] is employed to express the fact that a logical form containing
an argument identifier x is equal to the application of the abstraction P
to x. The identifier meta-variable X in P[X] ranges over such identifiers (x, y, z,
.), which are notated in lower-case italics (and are always ground).
The meta-variable P ranges over logical form abstractions missing one argument
(for instance z.s(j,z)). When matching meta-variables in logical forms,
we will allow limited use of higher-order unification. For instance, one can match
P[X] to s(j,x) by taking
The vocabulary and the set of relators that we have just specified define
a group computation structure We will now describe a set of
acceptors A for this computation structure. We take A to be the set of elements
of F (V ) which are products of the following form:
where S is a logical form (S stands for "semantics"), and where each W i is a
phonological element (W stands for "word"). The expression above is a way of
encoding the ordered pair consisting of the logical form S and the phonological
string W 1 (that is, the inverse of the product Wn
A public result SWn
in the group computation structure
3 Expression meta-variables are employed in the grammar for forming the set of conjugates
ff exp ff \Gamma1 of certain expressions exp (in our example, exp is ev(N,X,P[X]) P[X] \Gamma1 ,
Conjugacy allows the enclosed material exp to move as a block
in expressions of F (V ), see sections 4 and 5.
l * louise
man
w * woman
ran
t(N) * the N
tt(N,X,P[X]) * N that ff

Figure

2: Generation-oriented rules
with acceptors ((V; R); the G-grammar -will be interpreted as meaning
that the logical form S can be expressed as the phonological string W 1
Let us give an example of a public result relative to the grammar of Fig. 1.
We consider the relators (instanciations of relator schemes):
and the quasi-relators:
Then we have:
which means that s(j,l) louise is the result of a computation
This result is obviously a public one, which means that the
logical form s(j,l) can be verbalized as the phonological string john saw louise.
Generation
Applying directly, as we have just done, the definition of a group computation
structure in order to obtain public results can be somewhat unintuitive. It is
often easier to use the preorder ! . If, for a; b; c 2 F (V ), abc is a relator,
then abc ! 1, and therefore b ! a . Taking this remark into account, it
is possible to write the relators of our G-grammar as the "rewriting rules" of
Fig. 2; we use the notation * instead of ! to distinguish these rules from the
parsing rules which will be introduced in the next section.
The rules of Fig. 2 have a systematic structure. The left-hand side of each
rule consists of a single logical form, taken from the corresponding relator in
the G-grammar; the right-hand side is obtained by "moving" all the remaining
elements in the relator to the right of the arrow.
Because the rules of Fig. 2 privilege the rewriting of a logical form into an
expression of F (V ), they are called generation-oriented rules associated with
the G-grammar.
Using these rules, and the fact that the preorder * is compatible with the
product of F (V ), the fact that s(j,l) louise
can be obtained in a simpler way than previously. We have:
l * louise
by the seventh, first and second rules (properly instanciated), and therefore, by
transitivity and compatibility of the preorder:
* john saw l * john saw louise
which proves that s(j,l) * john saw louise, which is equivalent to saying
that s(j,l) louise result.
Some other generation examples are given in Fig. 3.
The first example is straightforward and works similarly to the one we have
just seen: from the logical form i(s(j,l),p) one can derive the phonological
string john saw louise in paris.
4.1 Long-distance movement and quantifiers
The second and third examples are parallel to each other and show the derivation
of the same string every man saw some woman from two different logical forms.
The penultimate and last steps of each example are the most interesting. In the
penultimate step of the second example, fi is instanciated to saw
has the effect of "moving" as a whole the expression some woman y \Gamma1 to the
position just before y, and therefore to allow for the cancellation of y \Gamma1 and y.
The net effect is thus to "replace" the identifier y by the string some woman;
in the last step ff is instanciated to the neutral element 1, which has the effect
of replacing x by every man. In the penultimate step of the third example, ff
is instanciated to the neutral element, which has the effect of replacing x by
every man; then fi is instanciated to saw man which has the effect
of replacing y by some woman.
Remark. In all cases in which an expression similar to ff a
(with the a i arbitrary vocabulary elements), it is easily seen that, by giving
* s(j,l) in p
* john saw l in p
* john saw louise in p
* john saw louise in paris
woman
(by taking
* every man saw some woman
(by taking
ff \Gamma1 every man x
man saw y
(by taking
* every man saw some woman
(by taking man
* t(tt(m,x,s(l,x))) ran
* the tt(m,x,s(l,x)) ran
* the m that ff
* the man that ff
* the man that ff
* the man that ff
* the man that louise saw ran
(by taking

Figure

3: Generation examples
ff an appropriate value in F (V ), the a move arbitrarily to the left
or to the right, but only together in solidarity; they can also freely permute cycli-
cally, that is, by giving an appropriate value to ff, the expression ff a
ff can take on the value
a k a (other permutations are in general not possible).
The values given to the ff, fi, etc., in the examples of this paper can be understood
intuitively in terms of these two properties.
We see that, by this mechanism of concerted movement, quantified noun
phrases can move to whatever place is assigned to them after the expansion
of their "scope" predicate, a place which was unpredictable at the time of the
expansion of the quantified logical form. The identifiers act as "target markers"
for the quantified noun phrase: the only way to "get rid" of an identifier x is
by moving x \Gamma1 , and therefore with it the corresponding quantified noun phrase,
to a place where it can cancel with x .
The fourth example exploits a similar mechanism for handling relative clauses.
At the time the relative pronoun is produced, an identifier inverse x \Gamma1 is also
produced which has the capability of moving to whatever position is finally
assigned to the relative verb's argument x .
4.2 Word movement and group morphisms
The derivations of Fig. 3 show possible rewritings of the four given logical forms
into phonological strings. It is natural to ask whether these rewritings are the
only ones possible. That is in fact the case, but for now we will confine ourselves
to showing that the expression:
can only be rewritten into the phonological string:
every man saw some woman ;
whatever values one may choose for the expression meta-variables ff and fi. 4
We start by considering a variant of the original vocabulary V , namely the
vocabulary are new letters not appearing in
. We then consider the application OE reduced
expression g of F (V ) into the expression of F (V 0 ) obtained by replacing each
x by a \Gamma1 every man (resp. man \Gamma1 every \Gamma1 a), and similarly by
replacing each y (resp. y \Gamma1 ) in g by b \Gamma1 some woman (resp. woman
The application OE is clearly a group morphism from F (V ) to F (V 0 ); in fact
it is an isomorphism, where OE \Gamma1 maps a (resp. b) into every man x
some woman y
We then consider the vocabulary V and the application
obtained by mapping, in reduced expressions of F (V 0 ),
4 Of course, for certain values of ff; fi, the first expression does not rewrite into a phonological
string at all.
OE
oe

Figure

4: Group morphisms between free groups over different vocabularies.
The group F (V ) is isomorphic to F (V 0 ), which in turns projects onto F (V 00 ).
The "phonological" subgroup F (V phon ) is kept invariant in the three morphisms.
each a (resp. a 1. This is again clearly a group morphism, and
we can consider the composition of morphisms
Fig. 4). This morphism oe has the following properties:
ffl It maps all phonological strings into themselves.
ffl It maps x (resp. y) into every man (resp. some woman).
ffl It maps
into
every man saw b
some woman );
that is, into every man saw some woman :
Because phonological strings are kept invariant in the mapping oe, whenever
one gives values to ff; fi such that fl is a phonological string, then, for these
values, but we have just seen that, for any values of ff; fi one has
man saw some woman . This establishes the initial claim.
This simple proof illustrates clearly the power of group operations. By changing
the presentation of the group F (V ) into an isomorphic one in which x; y have
been reexpressed in terms of a; b and of phonological elements, one obtains effects
which can be interpreted as constituent movements which furthermore are
mandatory if the output is constrained to be a string containing only phonological
elements.
Parsing
To the compatible preorder ! on F (V ) there corresponds a "reverse" compatible
preorder defined as a equivalently, a . The
normal submonoid M 0 in F (V ) associated with + is the inverse monoid of the
normal submonoid M associated with ! , that is, M 0 contains a iff M contains
a
It is then clear that one can present the relations:
A
etc.
in the equivalent way:
ran
some
etc.
louise
man
woman
ran
in
the
every
some
that

Figure

5: Parsing-oriented rules
Suppose now that we move to the right of the + arrow all elements appearing
on the left of it, but for the single phonological element of each relator. We
obtain the rules of Fig. 5, which we call the "parsing-oriented" rules associated
with the G-grammar.
By the same reasoning as in the generation case, it is easy to show that any
derivation using these rules and leading to the relation PS +LF , where PS
is a phonological string and LF a logical form, corresponds to a public result
in the G-grammar.
A few parsing examples are given in Fig. 6; they are the converses of the
generation examples given earlier.
In the first example, we first rewrite each of the phonological elements into
the expression appearing on the right-hand side of the rules (and where the meta-variables
have been renamed in the standard way to avoid name clashes). The
rewriting has taken place in parallel, which is of course permitted (we could have
obtained the same result by rewriting the words one by one). We then perform
certain unifications: A is unified with j, C with p; then B is unified to l.
Finally
5 Another possibility at this point would be to unify l with E rather than with B. This
would lead to the construction of the logical form i(l,p), and, after unification of E with
john saw louise in paris
every man saw some woman
and then either:
the man that louise saw ran

Figure

Parsing examples
E is unified with s(j,l), and we obtain the logical form i(s(j,l),p). In this
last step, it might seem feasible to unify E to i(E,p) instead, but that is in fact
forbidden for it would mean that the logical form i(E,p) is not a finite tree, as
we do require. This condition prevents "self-cancellation" of a logical form with
a logical form that it strictly contains.
5.1 Quantifier scoping
In the second example, we start by unifying m with N and w with M; then we
next to s(A,B) by taking again we "move"
next to s(A,B) by taking unified with
A and y with B. This leads to the expression:
where we now have a choice. We can either unify s(x,y) with Q[y], or with P[x].
In the first case, we continue by now unifying P[x] with
sm(w,y,s(x,y)), leading to the output ev(m,x,sm(w,y,s(x,y))). In the second
case, we continue by now unifying Q[y] with
ev(m,x,s(x,y)), leading to the output sm(w,y,ev(m,x,s(x,y)). The two possible
quantifier scopings for the input string are thus obtained, each corresponding
to a certain order of performing the unifications.
In the last example, the most interesting step is the one (third step) in which
ff is instanciated to s(l,B) \Gamma1 , which has the effect of "moving" x close to the
"missing" argument B
of "louise saw", to cancel it by unification with B and
consequently to fill the second argument position in the logical form headed by
s. After this step, P[x] is ready to be unified with s(l,x), finally leading to
the expected logical form output for the sentence.
6 Diagrams
6.1 Definition
Definition. A diagram over the vocabulary V is a finite graph which is (1)
planar, that is, embedded in the plane in such a way that the edges do not cross;
(2) connected; (3) directed, that is, the edges carry an orientation; (4) labelled,
that is, each edge carries a label taken in V .
A diagram separates the plane in n+1 connected open sets: the exterior (set
of points that can be connected to a point at infinity without crossing an edge),
that logical form, would conduct to the output s(j,i(l,p)). If one wants to prevent this
output, several approaches are possible. The first one consists in typing the logical form with
syntactic categories. The second one is to have some notion of logical-form well-formedness
(or perhaps interpretability) disallowing the logical forms i(l,p) [louise in paris] or i(t(w),p)
[(the woman) in paris], although it might allow the form t(i(w,p)) [the (woman in paris)].
6 We have assumed that the meta-variables corresponding to identifiers in P and Q have
been instanciated to arbitrary, but different, values x and y. We leave a discussion of this
point to a future paper.
and n open internal regions each consisting of points which can be connected
without crossing an edge, but which are separated from the exterior. An internal
region will be called a cell.
An example of a diagram over the vocabulary fa; b; cg is given in Fig. 7.000000001111111111
c
a
c c O
c
a
c
a
a

Figure

7: A diagram.
The boundary of a cell is the set of edges which constitute its topological
boundary. The boundary of a diagram is the set of edges which are such that
all their points are connected to the exterior.
If one choses an arbitrary vertex (such as O in the figure) on the boundary of
a diagram, and if one moves on the boundary in a conventional clockwise fashion
(an orientation that we adopt throughout in the sequel), then one collects a list
of edges which are either directed in the same way as the movement, or contrary
to it. By producing a sequence of atoms, positive in the first case, negative in
the second one, one can then construct a word of F (V ); this word is said to be
a boundary word of the diagram.
6.2 Reduced diagrams
We will say that a diagram is reduced if there does not exist a pair of edges
with a common vertex O, with the same label, oriented oppositely relative to
O (that is, both edges point towards O or both point from O), and such that
at least one of the two "angles" formed by the two edges is "free", that is, does
not "contain" another diagram edge (see Fig. 8).
6.3 Cyclically reduced words
word w on V [ V \Gamma1 is said to be cyclically reduced iff every
cyclic permutation of it is reduced.
It is easy to see that (1) a reduced word is cyclically reduced iff it is not of
the form aw 0 a \Gamma1 with a an atom (positive or negative), (2) the conjugate class
of any word contains cyclically reduced words, which are cyclic permutations of
each other.
a
c
c
O
c
a
a

Figure

8: A reduced diagram. The diagram of the previous figure was not
reduced because of the two c edges outgoing from vertex O.
6.4 Relator cells
Consider a group computation structure loss of gener-
ality, it can be assumed that the relators in R are cyclically reduced, because
the result monoid is invariant when one considers a new set of relators consisting
of conjugates of the original ones. From now on, unless especially stated
otherwise, this assumption will be made for all relators considered.
Take any such cyclically reduced relator
construct a labelled cell in the following way: take a circle and
divide it in n arcs; label the clockwise-ith arc x i and orient it clockwise if e
anti-clockwise otherwise. The labelled cell thus obtained is call the relator
cell associated with r.
Rather than presenting the GCS through a set of relator words as we have
done before, it is now possible to present it through a set of relator cells; if one
gives such a set, a standard presentation of the GCS can be derived by taking an
arbitrary origin on each cell and "reading" the relator word clockwise from this
origin; the origin chosen does not matter: any other origin leads to a conjugate
relator, and this does not affect the notion of result.
6.5 Fundamental theorem of combinatorial group theory
We are now able to state what J. Rotman calls "the fundamental theorem of
combinatorial group theory" [15]. We give the theorem in a slightly extended
form, adapted to the case of the normal sub-monoid closure; the standard case
of normal subgroup closure follows immediately by taking a set or relators containing
along with r.
Theorem 1 Let be a group computation structure such that all
relators r 2 R are cyclically reduced. If w is a cyclically reduced word in F (V ),
then w 2 NM(R) if and only if there exists a reduced diagram having boundary
word w and whose regions are relator cells associated with the elements of R.
O

Figure

9: Star diagram.
The proof is not provided; it can easily be recovered from the property
demonstrated in [11] (chapter 5, section 1). The proof involves the following
remark. If one considers a product
arbitrary elements of F (V ), this product can be read as
the boundary word of the "star" diagram represented in Fig. 9, starting at O
and progressing clockwise.
This star diagram is in general not in reduced form, but it can be reduced
by a stepwise process of equating edges which do not respect the definition of a
reduced diagram.
Example. Let's consider a GCS with vocabulary set of
(cyclically reduced) relators
The cyclically reduced word c is an element of NM(R), for it can be
obtained by forming the product
If we form the star diagram for this product, we obtain the first diagram shown
in Fig. 10.
This diagram is not reduced, for instance the two straight edges labelled
c are offending the reduction condition. If one "stitches" these two edges
together, one obtains the second diagram in the figure. This stitching corresponds
to a one-step reduction of the boundary word of the first diagram,
into the boundary word of the second
By continuing in this way, one obtains the fifth
diagram of the figure, which is reduced, and whose boundary is the wanted
6.6 Linguistic examples
The previous considerations can be applied to the linguistic examples given in
the body of the article. Here we only consider examples which do not involve
a
c
c
O
c
a
a
a
c
c
c
c
a
O
a
a
c
c
c
a
a
c
a
c c O
a
c
c
a
c c O
a
a
c
a
c c O
c
a
c
a
a

Figure

10: Transformation of a diagram into reduced form (adapted from [11]).
long-distance dependencies; the more complex examples will be treated after we
have introduced multi-relators in 7.6.
l p
saw in
paris
louise
john
(1)

Figure

11: Cells associated with some grammar relators.
saw
john
louise
in
paris
l

Figure

12: A diagram establishing the relationship between a logical form and
a phonological string.
Let's consider the relator schemes, from Fig. 1:
l louise
A
In Fig. 11, cells (which we have numbered from 1 to 5) associated with
some instanciations of these schemes are shown. In Fig. 12 we construct a
reduced diagram whose cells are the relator cells of Fig. 11. The boundary
word of this diagram is the expression i(s(j,l),p) paris
john \Gamma1 . This proves that, in the G-grammar, the logical form i(s(j,l),p) is
associated with the phonological string john saw louise in paris. Note (1) the
analogy between reading the diagram from top to bottom (resp. bottom to top)
and a generation (resp. parsing) process. 7
7 G-grammars and rewriting
In the discussion of parsing and generation, we saw how a derivation according to
the rewriting rules of Figs. 2 and 5 is always "sound" with respect to the group
computation structure. We did not consider the opposite question, namely
whether it is "complete" with respect to it: can any public result relative to the
GCS be obtained by such rewritings? The answer to this question will be given
by theorems demonstrated below (theorems 4 and 7), which roughly state that
such a rewriting system is complete relative to the GCS if the system does not
contain "ground cycles", that is situations where a ground term T can derive
This condition is true of both the rewriting systems of Figs 2 and 5. For
instance, in the generation case, it can be checked that any ground logical form
that appears on the right-hand side of a rule of Fig. 2 is strictly smaller than the
ground logical form on the left-hand side, therefore precluding ground cycles.
This condition is related to the decidability of generation and parsing, and we
will prove in 8 that our G-grammar is finitely enumerable both in parsing and
in generation, that is, in the terminology of [6], that it is inherently reversible.
This property is difficult to guarantee in formalisms relying on empty categories
for long-distance dependencies, a problem which is avoided by the use group
structure for the same purpose.
7.1 Oriented relators and rewriting rules
Suppose an is a relator. This relator is said to be oriented at index
if a number i with 1  i  n has been chosen.
A QCF rule (QCF stands for "quasi-context-free") on F (V ) is a pair,
notated a 7! ff, with a
is a group computation structure, and if r is a relator in R
such that r = a an in F (V ), then the rule
a i 7! a
an
is said to be the rule associated with the relator r oriented at index
i.
7 There is also an analogy between a bottom-up reading and a chart parsing approach in the
case of this example. In more complex examples (for instance multi-word expression parsing)
a better analogy would be with Colmerauer's Q-systems [3]. However, both analogies break
down when considering examples involving long-distance dependencies.
If for each element in a set of relators R, an orientation is chosen, one says
that an orientation has been given to the GCS. By associating a QCF rule
to each relator, one obtains the QCF system associated with the orientation.
A derivation relative to a QCF system is a finite sequence
of elements (that is, of strings formed over elements of V or
their inverses) such that, for each i, there exists ff; fi
1. and a 7! b is a rule of the rewriting system [replace-
ment step],
2. or s i
If for two strings s and t in (V one can find a derivation
are identical, then we
will say that s derives into t and we will write s 7! t (using the same notation
as for rewrite rules; the context will make clear which case is intended).
The following proposition, stating that rewriting implies preorder, is
straightforward.
Theorem 2 If 7! is the derivation relation associated with an oriented GCS,
then, for any s; t 2
Proof. Immediate consequence of the fact that if r = a an is a relator, then
and therefore
an
ut
7.2 Anteriority
Let's consider the QCF system associated with an oriented GCS. If a and b are
elements there exists a rule in the system of the form:
a 7! ffbfi;
then we will say that a is immediately anterior to b relative to the system
(or, equivalently, relative to the oriented GCS). If there exists a finite sequence
b such that c i is immediately anterior to c i+1 then we will say
that a is anterior to b, which will be noted:
a  b:
We will say that the anteriority relation is acyclic iff it is never the case
that a  a. We will say that it is noetherian iff any "descending" chain
a 1  a noetherian it is a fortiori acyclic.
If a rule in the QCF system has left-hand side a, then a will be called the
mother of the rule (or, equivalently, of the oriented relator corresponding to
the rule). The set M of all rule mothers is a subset of the set of atoms
called the set of potential mothers associated with the QCF system. We
will note M \Gamma1 the set of atoms which are inverses of potential mothers.
7.3 Rewriting theorem (basic case)
We are now ready to state a theorem which provides conditions under which
the reciprocal of theorem 2 holds. We will only sketch proofs.
We first need a lemma.
Lemma 3 Suppose that \Delta is a diagram relative to an oriented acyclic GCS,
and also that the set of potential mothers does not simultaneously contain an
element and its inverse. Then there is a relator cell in this diagram such that
its mother m is on the boundary of the diagram.
Proof. Take any cell \Gamma in the diagram, and consider the mother m in this cell. If
m is on the boundary of the diagram, we are done. Otherwise, m is on an edge
separating \Gamma from another cell \Gamma 0 , and therefore m \Gamma1 is on the boundary of \Gamma 0 (as
a consequence of the clockwise orientations of the cells). Because the condition
about potential mothers, m \Gamma1 cannot be the mother of \Gamma 0 , and therefore the
mother m 0 of \Gamma 0 is anterior to m. If m 0 is on the diagram boundary, we are done,
otherwise we repeat the operation. Because the anteriority relation is acyclic,
the iteration must stop at some point, which proves the lemma. ut
We can now state the theorem.
Theorem 4 If ' 7! ' is the derivation relation associated with an oriented GCS
where (i) anteriority is acyclic, and (2) the set of potential mothers does not contain
simultaneously an element and its inverse, then, for any s 2
and for any t 2 ((V
Proof. Suppose that s ! t, then there exists a diagram \Delta having k cells whose
boundary is st \Gamma1 . We will prove the result by induction on k. In the base case
the result is immediate, because in a diagram with 0 cells of boundary
st one necessarily has t.
Let's now address the case of k ? 0. From the lemma, there is a cell \Gamma in this
diagram whose mother m lies on the boundary of \Delta. Because of the condition
on t, this m cannot lie in the t portion of the boundary, and so it must lie in
the s portion (see Fig. 13).
The boundary of \Gamma can be written in the form mw \Gamma1 for some word w 2
therefore s can be expressed in the form
and s 2 subparts of s (see Fig. 14). But now one has:
by definition of the rewriting relation. Furthermore the word
is on the boundary of a diagram in cells, obtained from \Delta by removing the
we will not explain here in detail what it means to "remove a
cell", and will not justify formally why the remaining construct is still a diagram,
but the way the operation works may be understood on the basis of an example
(see Fig. 15). We now have:
and, by the induction hypothesis, one has
and therefore
ut
A
s
G

Figure

13: The diagram \Delta in k cells, whose boundary is st \Gamma1 . The word s can
be read clockwise from vertex A to vertex D, the word t counter-clockwise from
A to D. There exists a cell \Gamma whose mother m lies on the s portion of the
boundary.
7.4 G-grammars compared to CFG's, DCG's and Categorial
Grammars
Rather than starting from a G-grammar and associating rewriting systems to it,
one can start from a conventional grammar represented as a rewriting system
A

Figure

14: Removing the cell \Gamma by rewriting m into w.
and associate to it a G-grammar. An obvious question is then whether the
input-output relationship as defined in the two models agree.
Let's for instance consider the context-free grammar presented in Fig. 16, (a).
The rewriting system (a) is a QCF system associated with an orientation of the
G-grammar given in (a'), over the vocabulary U is the set
of nonterminals fs; np; vpg and W is the set of terminals john ; walked; often.
By Theorem 2, if we can derive a string of words wn from s, then
wn relative to the G-grammar.
However, the system (a) is not acyclic for anteriority, because of its fourth
rule. The translation of this rule is the relator vp vp
often \Gamma1 which is equal to
often \Gamma1 . This means that often often. This in turn,
because of the compatibility of the preorder, implies that, whenever one has
then one has s ! ff often fi, for any ff; fi 2 F (V ). In particular one has
string that cannot be derived from grammar (a). More
generally, it can be shown that, relative to the GCS, the word 'often' can be
added freely in any string generated from s!
One way of making the grammar (a) acyclic is to upgrade it to a Definite
Clause Grammar [13] such as (b). With each nonterminal is associated a term
representing the syntactic structure of the string spanned by this nontermi-
nal. The crucial point here is that the structure of the mother nonterminal (for
instance vp(.(often,VP))) strictly contains the structures of the daughter non-terminals
(for instance vp(VP)). It is then easy to show that the system is acyclic.
Then Theorem 4 holds, and the notions of derivations relative to (b) and (b')
coincide. In the example, the relator vp(:(often; VP))vp(VP)
does not
collapse to often \Gamma1 anymore, for vp(:(often; VP))
can never cancel out. From theorem 4, we now see that (b) and
(b') are equivalent.
Another way to obtain an acyclic grammar is shown in (c). Here we have
an infinite set of rules indexed by integers corresponding to string length. The
length of a mother nonterminal is strictly larger than the length of any daughter,
saw
john
louise
in
paris
l
saw
john
louise
in
paris
l

Figure

15: A cell-removal step. If one assumes that s(j,l) in p 7!
john saw louise in paris, then one has i(s(j,l),p) 7! s(j,l) in p 7! john
saw louise in paris.
and this again ensures acyclicity.
7.4.1 G-grammars and categorial grammars
The context-free grammar (a) and its associated G-grammar (a') can be used
to illustrate a crucial difference between G-grammars and categorial grammars.
Whereas, in categorial grammar, the expression vp=vp "expects" a vp on the
right - and nothing else - and then "returns" a vp, when working with groups,
an expression such as vp vp \Gamma1 is formally undistinguishable from 1. It is this
crucial property that permits G-grammars to profit from many standard mathematical
tools.
(a) s 7! np vp (a') s vp
vp 7! walked vp walked \Gamma1
vp 7! often vp vp vp
(b)
vp(walked) 7! walked vp(walked) walked \Gamma1
(c) s(x+y) 7! np(x) vp(y) (c') s(x+y) vp(x)
walked walked

Figure

G-grammars.
7.5 Mixing commutative and non-commutative phenom-
ena, logic programs
We have already seen examples where commutative and non-commutative aspects
are both present in a lexical entry. Thus, the presence of ff; ff \Gamma1 in the
entry for 'every' in Fig. 2 allows the expression every N X
to move as a block
to the position where the argument X of the verb is eventually found; in this
movement, it is however impossible for every and N to exchange their relative
positions, and it can be shown that, for the input logical forms of Fig. 3, only
the four phonological strings listed can be obtained.
Let us briefly indicate how this commutative/non-commutative partnership
could be used for error correction purposes. Suppose that a relator of the
Report is added to the grammar, where Error is some
erroneous input (for instance it could be the word 'principle' improperly used
in a situation where 'principal' is needed), Repair is what the input should have
been (in our example, the word 'principal'), and Report is a report which tells
us how the error was corrected. Then, the expression Error \Gamma1 Repair can move
in block to the spot where the error occurs, replacing the erroneous word by the
correction and allowing normal processing to continue. The report can then be
used for warning or evaluation purposes.
Fully commutative structures and logic programs Suppose that one
wants to have a group computation structure which is completely commutative,
that is, one in which elements can move freely relative to each other. This property
could be stipulated by introducing a notion of "commutative group compu-
tation" using the free commutative group FC(V ) rather than F (V ). Another
possibility, which illustrates the flexibility of the group computation approach,
is just to add a relator scheme fffiff to R, where ff and fi are expression
meta-variables. This expression is called a commutator of ff and fi because when
multiplied by fiff it yields fffi. This single relator scheme permits to permute
elements in any expression, and has the same effect as using FC(V ).
An example where commutative structures are useful is the case of logic
programs. It can be shown that if one encodes a clause of a logic program
in a commutative structure,
and defines public results to consist of a single ground predicate P , then public
results in the group computation structure coincide with consequences of the
program. 8
7.6 Multi-relators
Theorem 4 already gives interesting equivalence for several types of GCS's, such
as the ones associated with acyclic DCGs, or for a G-grammar which does not
make use of expression meta-variables, such as the G-grammar obtained by
eliminating the entries for every, some and that from the G-grammar of Fig. 1.
However, it is not sufficient for the long-dependency situations such as these
where expression meta-variables do appear; in these cases, the conditions of
Theorem 4 are not met, because by giving a well-chosen value to the expression
meta-variable, the condition of anteriority can be easily violated.
We need a stronger version of the theorem which is able to take into account
the situation where expression metavariables appear in pairs ff; ff \Gamma1 . In
order to state this extended version of Theorem 4, we need to introduce some
terminology.
Consider a finite list wn of elements of (V
wn ) be the set:
The following lemma is straightforward.
Lemma 5 . The set MC(w wn ) has the following properties:
ffl It is a normal subset of F (V ) (that is, is self-conjugate);
ffl It is invariant up to arbitrary permutations of the list
ffl It is invariant up to cyclic permutations of any of the words w
be the set:
wn ) is the set of conjugates of elements of B in F (V ).
8 This result, in contrast to the corresponding result concerning DCG's (see below) does
not depend on a condition of acyclicity. This difference is related to the fact that, in the case
of logic programs, a succesful sequence of rewritings results in the empty string, whereas in
the case of DCGs, it results into a string of words. The acyclicity condition for DCGs ensures
that this string of words contains all words that could be produced using the GCS. For logic
programs, this property is irrelevant.
l louise
man
ran

Figure

17: Multi-relator version of our example G-grammar. We have made
use of the transformations permitted by Lemma 5.
Because of the second of these properties the set MC(w wn ) is defined
as soon as the multiset (unordered list) hw wn i, which we will call a multi-
relator, is given. We will call MC(w wn ) the set of multi-conjugates
of the multi-relator hw wn i.
If we are given a (finite or infinite) collection MR of multi-relators, we can
consider the group computation structure obtained by taking as set R of relators
the set
We will call the GCS thus obtained the group computation structure
with multi-relators
When presenting a group computation structure with multi-relators, we will
sometimes use the notation:
wn
for listing the multi-relators.
With such a notation, the presentation of our example G-grammar of Fig. 1
becomes the presentation shown in Fig. 17.
The presentation of the grammar using multi-relators is more symmetrical
than that of Fig. 1. Remark that expression meta-variables are not used anymore

7.6.1 Multi-relators and diagrams
We will now state a theorem which is an extension of the the fundamental
theorem of combinatorial group theory for the case of GCS's with multi-relators.
We first need the notion of multi-cell associated with a multi-relator.
We first remark that we can always assume that a multi-relator
wn i is such that each w i is cyclically reduced, because taking the
cyclically reduced conjugate of w i does not change the notion of multi-conjugate.
We will assume this is always the case in the sequel.
wn i is a multi-relator, and if \Gamma i is the cell associated with w i in
the manner of 6.4, then we will call the multiset of cells
ng the multi-cell associated with this multi-relator.
Consider a finite multiset of multi-relators and take the multi-set obtained by
forming the multiset
U
k \Theta k of the multi-cells associated with these
multi-relators. A diagram whose cells are exactly (that is, taking account of the
cell counts) those of the
multiset\Omega will be said to be a diagram relative to
the GCS with multi-relators under consideration.
Theorem 6 . Let be a group computation structure with
multi-relators. If w is a cyclically reduced word in F (V ), then w is in the
result monoid of GCS-MR iff there exists a reduced diagram relative to GCS-MR
having boundary w.
The proof of this theorem is a straightforward extension of the proof of
Theorem 1 and is not provided.
7.6.2 Linguistic examples
These results can now be applied to a diagrammatic proof of the fact that, in
our example G-grammar, one has (see 4.1):
every man saw some woman:
In Fig. 18 we show multi-cells corresponding to the G-grammar entries relevant
for this example (see Fig. 17), and in Fig. 19 a diagrammatic proof of the
example; the multi-cells are lettered (1) to (5) for easy comparison between the
figures.
7.6.3 Multi-relators and QCF systems
One can extend the notion of orientation of 7 to multi-relators in the following
way. We will say that a multi-relator hw wn i is oriented at index
if one of the words w i has been chosen and if, writing w
, with
an index j with 1  j  m i has also been chosen. The QCF rule
scheme associated with the oriented multi-relator is then the rewriting scheme:
a ij 7! a i(j \Gamma1)
Y
where the ff k are expression metavariables (which can therefore take arbitrary
values in F (V )).
One can extend the notion of anteriority to oriented multi-relators. We simply
define the atom a ij to be anterior to each of the atoms a kl \Gamma1 appearing in the
man
(1)
saw
x y
every m
woman
(2)
y
some w

Figure

18: Multi-cells for some multi-relators in the grammar. Dotted lines
indicate that two cells are part of the same multi-cell: they will appear together
in a diagram or not at all.
right-hand side of the rewriting rule, that is to say, all inverses of atoms appearing
in any of the w k , apart of course from a ij \Gamma1 itself, and not considering the
atoms appearing in any of the ff k ; ff k \Gamma1 (it follows that the anteriority relation
is defined between atoms or inverses of atoms that appear in hw wn i).
The notion of acyclic and noetherian QCF system is defined just as before
on the basis of this anteriority relation.
The following theorem is a straightforward extension of Theorem 2.
Theorem 7 If 7! is the derivation relation associated with an oriented multi-
relator GCS, then, for any s; t 2
saw
every
x
man
woman
y
some
(1)
(2)

Figure

19: A diagram using multi-cells establishing a relationship between
the sentence every man saw some woman and its logical form
ev(m,x,sm(w,y,s(x,y))).
7.6.4 Rewriting theorem (multi-relator case)
We now state a theorem which extends Theorem 4 to the case of multi-relators
GCS's. The proof is only broadly outlined.
Theorem 8 If ' 7! ' is the derivation relation associated with an oriented multi-
relator GCS where (i) anteriority is acyclic, and (2) the set of potential mothers
does not contain simultaneously an element and its inverse, then, for any s 2
Proof. Rough sketch. The proof is similar to that of theorem 4. The difference
is that we must perform multi-cell removal rather than simple cell-removal, and
that this may involve more complex "topological surgery". An example may
serve to illustrate the general method. Let's consider a GCS defined by the
three multi-relators: hfd
these multi-relators are oriented by distinguishing f in the first, d in the sec-
ond, and a in the third. Then the corresponding rewriting system has the rules:
is an expression
meta-variable. Anteriority is clearly acyclic. Let us now consider the diagram
\Delta at the top-left of Fig. 20. This diagram contains three multi-cells corresponding
to the three grammar multi-relators, one of which, \Gamma, is itself formed of two
cells, and corresponds to the third multi-relator. The mother in each multi-cell
is underlined. By reading the boundary of the diagram, we see that a ! hm.
We want to show how multi-cell removal can be used to obtain a 7! hm. First,
by a reasoning similar to the proof of Lemma 3, we know that some mother
must appear on the boundary. In the example, this is a. We want to remove
the corresponding multi-cell \Gamma from the diagram without destroying the
topological property of being a diagram, and, in particular, without destroying
simple-connectivity. In order to do that, we have to find a "subdiagram" (that,
is, a topological constructs which is itself a diagram) \Delta 0 of \Delta consisting only
of the cells appearing in the multi-cell under consideration (simple reasoning
shows this to always be possible). In our example this subdiagram is constituted
by the two cells labelled \Gamma linked by the edge labelled d. The surgery now
consists in "forming a tube" wherever a "thin" edge, that is, an edge which is
not on the surface of a subdiagram cell, such as the d edge in the example, and
in deleting from the diagram both the subdiagram cells and the "tubes" thus
formed. What remains is a well-formed diagram - which may well have thin
edges itself - in which the removed tubes leave behind couple of parallel edges
carrying the same label (second diagram in our figure, consisting of two cells).
This multi-cell removal corresponds to a rewriting of the multi-cell mother into
a right-hand side, where expression multi-variables have been given proper values
(in our example ff takes the value c \Gamma1 d) allowing for the construction of the
subdiagram. The operation is repeated until all multi-cells have been deleted,
in the same way as in the previous proof.
In the example given in illustration, after the first multi-cell, having its
mother a on the diagram boundary, has been removed, one obtains the second
diagram; at this point a has been rewritten (using the rewriting rule for a) into
a 7! bc c c. The new diagram contains two multi-cells, each
consisting of a single cell. Again, there exists a mother on the diagram bound-
ary, this time f . The corresponding cell is removed, and at this point a has been
rewritten (using the rewriting rule for f) into bdeg
The last cell, with mother d is finally removed, leaving the last diagram (with
only edges, but no cell).
At this point a has been finally rewritten (using the rewriting rule for d) into
Application to G-grammars When the G-grammar presented as a multi-
relator GCS in Fig. 17 is oriented by privileging as a left-hand side the "largest"
logical-form atom, its associated QCF system becomes the system of Fig. 2. It
can be checked that this "generation" system is acyclic and even noetherian.
The theorems 7 and 8 then say that generation by using the rewriting system
is equivalent to generation by using the G-grammar. A similar result can be
shown for the "parsing-oriented" rewriting system of Fig. 5.
f
d
c
e
d
f
a
d
c
e
G
G
e

Figure

20: Multi-cell removal and rewriting.
Computability
We will not attempt here a systematic treatment of the computability properties
of G-grammars, but will limit ourselves to prove certain strong decidability
properties of our example G-grammar. Although a general synthesis is not
proposed here, the methods show clearly the power of group morphisms to
study computability in group computation structures.
If we consider a grammar to be the specification of a recursively enumerable
list L of pairs (sem; phon), then, using the terminology of [6], we will say that
generation (resp. parsing) is finitely enumerable if the subset of L consisting of
the pairs (sem; phon) with sem known (resp. with phon known) is finite and
computable in finite time. If parsing and generation are both finitely enumer-
able, the grammar is said to be inherently reversible. We will sketch a
proof of the fact that the G-grammar of Fig. 17 is inherently reversible. 9
9 In [6], several types of computability of generation (resp. parsing) are defined and it is
shown there that, unless certain specific conditions are met, whatever the type of computability
considered, the computability of parsing and the computability of generation bear in general
no relation to each other.
8.1 Bounding of diagram complexity in function of the
input
Let's first consider a group morphism f from F (V ) to the additive group of
reals (R;+). Thus f is a real-valued function on F (V ) which is such that for
f(a)+f(b). Remark that because f takes its value
in a commutative group, f is invariant by permutations (that is,
We can therefore define the value of f on a multi-relator
be its value on any of its multi-conjugates, that is, to be f(r 1
If a result s is obtained by taking the product of multi-conjugates of the multi-
relators can be computed simply by taking the sum of
all the multi-relator components r ij , where mr
i.
Let's now suppose that there exists a strictly positive real ! such that, for
any multi-relator mr in the group computation structure, one has:
If such is the case, we will then say that f is a relator-lower-bounded or rlb
morphism.
Similarly, we will say that f is a relator-upper-bounded or rub morphism iff
there exists a strictly positive real ! such that, for any multi-relator mr in the
group computation structure, one has:
The following property is immediate.
Lemma 9 If f is an rlb morphism from F (V ) to R, and if s is a result in the
GCS, then (1) f(s)  0, and (2) if a computation of s involves k multi-relators,
then k  f(s)=!. Similary, if f is an rub morphism, then, if a computation of
s involves k multi-relators, then f(s)  k!.
If f is rlb, and if s an expression in F (V ) for which the value of f is known,
then we see that in order to test whether s is a result, we only need to test
diagrams with an a priori bounded number of multi-cells.
Now consider the following two real-valued functions on F (V
ffl For e 2 F (V ), e reduced, f(e) is defined as the difference between the
number of phonological elements which appear in e with a negative
polarity with the number of such elements which appear with a
positive polarity. For instance the value of f on john \Gamma1 s(j; m) in the park
ffl Suppose that the size of a term T is defined recursively by the following
equations: (1) if T is an argument identifier (such as x, y, .) then
is of arity 0, then
of arity n, of the form
being the sum of the
sizes of the terms of positive polarity minus the sum of the sizes of the
terms of negative polarity. For instance, the value of g on the expression
It is immediate that f and g are morphisms. It is also a simple observation
that, for any multirelator mr of Fig. 17, the value of both f and g on mr
is uniformly lower-bounded by and g are uniformly
equal to 1 in our example). For instance if e is any expression of the form
1. It is also clear that both f and g are uniformly upper-bounded

Let's now consider parsing. In this case, we are looking at all results of the
form sem phon \Gamma1 , with phon known, and therefore with f known (it is just the
length of the phonological string). We therefore have only to consider diagrams
with fewer than length(phon) multicells and having a boundary of the form
sem phon \Gamma1 .
If we instead consider generation, we are looking at all results of the form
sem phon \Gamma1 , with sem known, and therefore with g known. We therefore have
only to consider diagrams with fewer than size(sem) multicells and having a
boundary of the form sem phon \Gamma1 .
8.2 Restriction of the set of multi-cells to consider
We are now very close to results of finite enumerability for parsing and genera-
tion. We know a bound for the total number of cells in any relevant diagram.
Still, it could be conceivable that the repertory of relevant cells is not finite. We
will now show that this cannot be the case.
Let's introduce the notion of subharmonic function on a GCS. 10 Let h be a
function from V [ V \Gamma1 to R. We will say that h is subharmonic relative to the
GCS if, for any diagram \Delta relative to the CGS, h can only reach its maximum
on the boundary of \Delta (therefore not on an "internal" edge in the diagram).
Let's define h as the function which takes a phonological element, whatever
its polarity, to 0, and which takes a logical form T , as well as its inverse T \Gamma1 , to
From the discussion of acyclicity of our G-grammar, and from Lemma
3, we see that h is subharmonic for the G-grammar.
This means that any multi-cell appearing in a diagram which is a proof of
sem phon \Gamma1 has all its semantics (of whatever polarity) bounded by the size of
sem.
It is easy to check that there are only finitely many multi-cells according to
the G-grammar for which the largest semantic element has a bounded size. 11
10 The terminology is borrowed from analysis, where subharmonic functions are functions
which have a property of reaching their maximum only on the boundary of disks.
11 We are finessing the case of the identifier meta-variable X , whose domain of instanciation
has not been described precisely. We will assume here that its domain of instanciation is
constituted by a finite, fixed, set of identifiers x; This can be assumed both for generation
and for parsing on the basis of a simple argument. A more satisfying treatment is left to future
research.
So, if we are in generation mode, and know sem, we have only a fixed, finite,
repertory of multi-cells to consider for diagrams pretending to the status of
proofs of a result of the form sem phon \Gamma1 . Because of the fact noted above that
these cells can appear conjointly only a finite number of times, we have now
proven the finite enumerability of generation.
For parsing, we only know phon. But it is immediate from the fact that f is
rlb and g rub that sem can be bounded from the fact that phon is known. We
conclude that only a finite repertory of cells have to be considered for diagrams
pretending to the status of proof of results of the form sem phon \Gamma1 . By the
same reasoning as previously, this proves the finite enumerability of parsing.

Acknowledgements

Thanks to Sylvain Pogodalla, Christian Retor'e and to the anonymous reviewers
for their remarks and comments.



--R



'Les syst'emes-Q ou un formalisme pour analyser et synth'etiser des phrases sur ordinateur'

'Transformations de grammaires logiques et r'eversibilit'e en Traduction Automatique'.



Presentations of Groups.

Combinatorial Group Theory.
Lambek grammars are context free.

'R'eseaux et s'equents ordonn'es'.
An Introduction to the Theory of Groups.
Essays in Logical Semantics.

--TR
parsing;generation;group theory;diagrams