Modeling Coordination by Means of Operations on Strings and on Derivation Trees

Carlos Martín-Vide^{∗} Gheorghe Păun^{†}^{‡}

Abstract

Several operations on strings are introduced, as models of the phenomenon of coordination in natural languages. Their relationships with other string operations is investigated. On this basis, the closure properties of families in the Chomsky hierarchy are obtained. In particular, we prove that the family of context-free languages is not closed under all but one of these operations. This special case concerns the coordination defined only between strings with a common syntactic structure (both strings have derivations described by identical trees, modulo the coordinated subwords). Some interpretations of these results are mentioned.

1 Coordination; Some Variants

The idea we start from is that in a given coordinated structure all the conjuncts are of the same type and status, and the coordination as a whole is of the same type and status as its subparts. This means that it is not possible to define only one head in the construction (coordination is not a projection of the conjunction, and there is no dependence between the two conjuncts), making it impossible to apply any general principle of hierarchical construction of the sentence (X-bar, for instance).

Coordination is basically a recursive phenomenon, because it builds phrase structures (trees associated to strings) of any length. Several studies of coordination start from the following generalization due to Chomsky, Chomsky (1957):

If S_{1} and S_{2} are grammatical sentences, and S_{1} differs from S_{2} only in that X appears in S_{1} where Y appears in S_{2} (i.e., S_{1} = … X … and S_{2} = … Y …), and X and Y are constituents of the same type in S_{1} and S_{2}, respectively, then S_{3} is a sentence, where S_{3} is the result of replacing X by X + and + Y in S_{1} (i.e., S_{3} = … X + and + Y …).

∗Research Group on Mathematical Linguistics and Language Engineering (GRLMC)

†Institute of Mathematics of the Romanian Academy

‡Research supported by the Secretaría de Estado de Universidades e Investigación – SAB95-

The usual treatment of coordination phenomenon starts from the idea that two categories can be catenated with a conjunction giving a larger category of the same type. The classical rule of this description obeys the context-free requirements, where X can be any linguistic category or nonterminal: X → X and X.

This schema can produce the well-known coordination cases between equal categories, which are common in all languages. Several problems arise if we include the treatment of the following cases of coordination:

1. Coordination of unlike categories. The general schema for this kind of sentences is similar to Z → Y and X, as appearing in the following examples Sag, Gazdar, Wasow, and Weisler (1985):

a. Pat is stupid and a liar (AP and NP).

b. Pat is a Republican and proud of it (NP and AP).

c. Pat is healthy and of sound mind (AP and PP).

d. That was a rude remark and in very bad taste (NP and PP), where X and Y are different categories or nonterminals and Z is any category resulting from both X and Y. The problem in this schema is to explain how Z is constructed, because it is neither equal to X nor equal to Y (and therefore the rule is not recursive).

2. Binary coordination between many pairs of nonterminals. The following sentences are typical for a language of the form {a^{n}b^{m}c^{n}d^{m} | n, m ≥ 1}, possessing crossed dependencies which cannot be produced by means of context-free rules without regulation:

a. John sent a letter and a postcard to Mary and to Paul, respectively.

b. The boys and the girls eat apples and bananas, respectively.

c. The boys and the girls run and walk through the garden, respectively.

d. ∗John and Mary sings and dances, respectively.

3. Non-constituent coordination and gapping phenomena. English and other languages contain a number of coordinate constructions where the conjuncts are not constituents in the normal sense but are sequences of constituents. The general term for such constructions is non-constituent coordination:

a. Mary studies art, John, music and Paul, history.

b. Harry has sent a letter to Mary, and John, a postcard to Paul.

c. Paul composed, and John posted, a letter to Mary.

Conjunctions can be performed in ordered pairs, where the order of the elements is fixed. The members of a couple may be the same (o … o (Spanish), et … et (French)) or different (both … and (English)). One calls binary coordination the structure which has two conjuncts, and multiple coordination the structure with more than two. This may express a restriction over the set of conjunctions: but cannot appear in multiple coordination, and neither the couples with different words, as in the case of both … and. All languages use this kind of structures, and this assumption suggests a unified treatment of the phenomenon. We try to do this in terms of formal operations on strings and languages.

2 Formal Language Prerequisites

As usual, V^{∗} denotes the free monoid generated by the alphabet V with respect to the operation of concatenation; λ stands for the empty string, V^{+} = V^{∗} −{λ}, and |x| is the length of x ∈ V^{∗}. The set of all prefixes of x ∈ V^{∗} is denoted by P ref(x). The right derivative of a language L ⊆ V^{∗} with respect to a string x ∈ V^{∗} is defined by: ∂_{x}^{r}(L) = {y ∈ V^{∗} | yx ∈ L}. The shuffle of two strings x, y ∈ V^{∗} is defined by: x ⊔ ⊥ y = {u_{1}v_{1} … u_{n}v_{n} | n ≥ 1, x = u_{1} … u_{n}, y = v_{1} … v_{n}, u_{i}, v_{i} ∈ V^{∗}, 1 ≤ i ≤ n}. For L_{1}, L_{2} ⊆ V^{∗} we write L_{1} ⊔ ⊥ L_{2} = ⋃_{x∈L_{1},y∈L_{2}}(x ⊔ ⊥ y).

A context-free grammar is denoted by G = (N, T, S, P), where N is the nonterminal alphabet, T is the terminal alphabet, S ∈ N is the axiom, and P is the set of productions, written as A → x, A ∈ N, x ∈ (N ∪ T)^{∗}. The derivation relation is denoted by ⟹, its reflexive and transitive closure by ⟹^{∗}; the language generated by G is denoted by L(G).

The families of regular, linear, context-free, context-sensitive, and recursively enumerable languages are denoted by REG, LIN, CF, CS, and RE, respectively.

A gsm (“generalized sequential machine”) is a system g = (K, V_{1}, V_{2}, s_{0}, F, δ), where K is the set of states, V_{1} is the input alphabet, V_{2} is the output alphabet, s_{0} ∈ K is the initial state, F ⊆ K is the set of final states, and δ is a mapping (called transition mapping) from K × V_{1} to the set of finite subsets of 2^{V_{2}^{∗}×K}. We extend δ to K × V_{1}^{∗} as follows:

δ(s, λ) = (λ, s),
δ(s, ax) = {(yx′, s′) | (x′, s′) ∈ δ(s′′, x), (y, s′′) ∈ δ(s, a)},

for all s ∈ K, a ∈ V_{1}, x ∈ V_{1}^{∗}. Then, for w ∈ V_{1}^{∗}, L ⊆ V_{1}^{∗}, we define

g(w) = {z ∈ V_{2}^{∗} | (z, s_{f}) ∈ δ(s_{0}, w), for some s_{f} ∈ F },

g(L) = ⋃_{w∈L} g(w).

A gsm is said to be λ-free if δ(s, a) ⊆ V_{2}^{+} × K, for all a ∈ V_{1}, s ∈ K.

It is known that the families in the Chomsky hierarchy are closed under λ-free gsm mappings.

A morphism h : V^{∗} → V^{∗} is said to have limited erasing on a language L ⊆ V^{∗} (in short, we say that h is limited on L) if there is a constant k such that |x| ≤ k|h(x)| for all x ∈ L, x ≠ λ.

All families in the Chomsky hierarchy are closed under limited morphisms. For further notions and results in formal language theory we use here, we refer

to Rozenberg and Salomaa (1997). We only recall here the important notion of a derivation tree.

Given a context-free grammar G = (N, T, S, P), a tree τ with the nodes labelled by elements of N ∪ T ∪ {λ}, is a derivation tree with respect to G if:

1. the root of τ is labelled by S,

2. if the descendents of a node labelled by some A ∈ N are α_{1}, α_{2}, …, α_{k}, k ≥ 1, α_{i} ∈ N ∪ T, then the production A → α_{1}α_{2} … α_{k} is in P, 3. if a node is labelled by λ, then it is the only descendent of a node labelled by

some A ∈ N and A → λ is a production in P,

4. the nodes labelled by elements of T ∪ {λ} have no descendents, all nodes labelled by elements of N have at least one descendent.

The nodes labelled by elements of T ∪{λ} constitute the frontier of τ (the other nodes – excepting the root – are said to be internal nodes); we denote by fr(τ) the string in T^{∗} identified by the frontier (we assume τ placed with the root above and we read fr(τ) from left to right, on the frontier nodes).

For a node ν in τ, we denote by τ(ν) the subtree of τ with the root in ν, by e(ν) the label of ν, and by fr(τ(ν)) the subword of fr(τ) corresponding to the frontier of τ(ν).

It is known that for every string w generated by a context-free grammar G there is a derivation tree τ with respect to G such that fr(τ) = w; if G is unambiguous, then τ is unique.

3 Two Basic Coordination Operations on Strings

Intuitively, for two strings x, y ∈ V^{∗} with a common prefix, x = ux′, y = uy′, the coordination of x, y leads to a string z = ux′y′ (or z = uy′x′, if the order is not relevant). We consider here two variants of this operation, depending on whether the common prefix is maximal or not.

To start with, let us denote by mp(x, y) the longest common prefix of x, y:

mp(x, y) = u iff x = ux′, y = uy′ and there is no u′ ∈ V^{∗}
such that x = u′x′′, y = u′y′′ and |u′| > |u|.

Then, the free prefix coordination of x, y is defined by:

C_{fp}(x, y) = {ux′y′ | x = ux′, y = uy′, for some u, x′, y′ ∈ V^{∗}},

whereas the maximal prefix coordination of x, y is defined by:

C_{mp}(x, y) = {ux′y′} iff x = ux′, y = uy′ u = mp(x, y), x′, y′ ∈ V^{∗}.

Observe that C_{fp}(x, y) can contain several strings, that always C_{mp}(x, y) ⊆ C_{fp}(x, y) and that C_{mp}(x, y) ≠ ∅ (at least λ ∈ P ref(x) ∩ P ref(y); if mp(x, y) = λ, then C_{mp}(x, y) = xy).

Each operation C_{α}, α ∈ {fp, mp}, is extended in the natural way to languages:

C_{α}(L) = ⋃_{x,y∈L} C_{α}(x, y).

In order to settle the closure properties of languages in the Chomsky hierarchy with respect to operations C_{α}, we use the following two auxiliary results, relating C_{α} to known operations on languages.

Lemma 1. If F L is a family of languages closed under union, concatenation with symbols, intersection with regular languages, and right derivative, then F L closed under C_{α}, α ∈ {fp, mp}, implies F L closed under intersection.

Proof. For a family F L as above, consider two languages L_{1}, L_{2} ∈ F L, L_{1}, L_{2} ⊆ V^{∗}, and construct:

L = L_{1}{cc_{1}} ∪ L_{2}{cc_{2}},

where c, c_{1}, c_{2} are symbols not in V. For the regular language R = V^{∗}{cc_{1}c_{2}} we obtain:

L_{1} ∩ L_{2} = ∂_{cc_{1}c_{2}}(C_{α}(L) ∩ R), α ∈ {fp, mp}.

(⊆) If x ∈ L_{1} ∩ L_{2}, then x_{1} = xcc_{1} ∈ L_{1}, x_{2} = xcc_{2} ∈ L_{2}. Clearly, mp(x_{1}, x_{2}) = xcc_{1}c_{2} ∈ C_{α}(L) ∩ R. Moreover, x = ∂_{cc_{1}c_{2}}^{r}(xcc_{1}c_{2}).

(⊇) Take x ∈ ∂_{cc_{1}c_{2}}^{r}(C_{α}(L) ∩ R). Then xcc_{1}c_{2} ∈ C_{α}(L) ∩ R, hence there are x_{1} ∈ L_{1}{cc_{1}}, x_{2} ∈ L_{2}{cc_{2}} such that xcc_{1}c_{2} ∈ C_{α}(x_{1}, x_{2}). Because xcc_{1}c_{2} contains one occurrence of c_{1} and one of c_{2}, we must have x_{1} = x′_{1}cc_{1}, x′_{1} ∈ L_{1}, and x_{2} = x′_{2}cc_{2}, x′_{2} ∈ L_{2}. Because xcc_{1}c_{2} contains only one occurrence of c, it follows that mp(x_{1}, x_{2}) = x_{3}c. Consequently, x′_{1} = x′_{2} = x_{3} = x. This implies that x ∈ L_{1} ∩ L_{2}.

From the closure properties of F L, we obtain that L ∈ F L; if C_{α}(L) ∈ F L, then also L_{1} ∩ L_{2} ∈ F L. ♢

Lemma 2. If F L is a family of languages closed under shuffle, λ-free gsm mappings, and limited morphisms, then F L is closed under C_{α}, α ∈ {fp, mp}.

Proof. Let F L be a family as above and take L ∈ F L, L ⊆ V^{∗}. Consider a new symbol, c ∉ V. For each a ∈ V, take a new symbol, a′, and denote V′ = {a′ | a ∈ V }. Consider the morphisms

h : V^{∗} ⟶ V^{′∗}, defined by h(a) = a′, for all a ∈ V,

h′ : (V ∪ {c})^{∗} ⟶ V^{∗}, defined by h′(a) = a, for a ∈ V, and h′(c) = λ.

Consider also the regular language

R = {aa′ | a ∈ V }^{∗}{c^{2}}V^{∗}V^{′∗}

and the gsm

g = ({s_{0}, s_{1}, s_{2}}, V ∪ V′ ∪ {c}, V ∪ {c}, s_{0}, {s_{2}}, δ),

with the mapping δ defined by

\begin{matrix}δ(s_{0}, a) = \{(a, s_{0})\}, a ∈ V, & δ(s_{1}, c) = \{(c, s_{2})\}, \\ δ(s_{0}, a′) = \{(c, s_{0})\}, a ∈ V, & δ(s_{2}, a) = \{(a, s_{2})\}, a ∈ V, \\ δ(s_{0}, c) = \{(c, s_{1})\}, & δ(s_{2}, a′) = \{(a, s_{2})\}, a ∈ V. \end{matrix}

Then we obtain:

C_{fp}(L) = h′(g(((L ⊔ ⊥ {c}) ⊔ ⊥ (h(L) ⊔ ⊥ {c})) ∩ R)). (∗)

(⊆) If x ∈ C_{fp}(L), then x = ux′y′, for some x_{1} = ux′, y_{1} = uy′, both in L. Then ucx′ ∈ L ⊔ ⊥ {c}, h(u)ch(y′) ∈ h(L) ⊔ ⊥ {c}. If u = a_{1}a_{2} … a_{k}, k ≥ 0, a_{i} ∈ V, 1 ≤ i ≤ k, then a_{1}a′_{1}a_{2}a′_{2} … a_{k}a′_{k}ccx′h(y′) ∈ ((L ⊔ ⊥ {c}) ⊔ ⊥ (h(L) ⊔ ⊥ {c})) ∩ R.

The gsm g works as follows:

– scanning a prefix b_{1}d′_{1}b_{2}d′_{2} … b_{r}d′_{r} ∈ (V V′)^{∗}, one produces b_{1}cb_{2}c … b_{r}c,

– when reading cc, these symbols are left unchanged,

– from now one, each a ∈ V remains unchanged, and each a′ ∈ V′ is replaced by a.

Therefore, g(a_{1}a′_{1} … a_{k}a′_{k}ccx′h(y′)) = a_{1}c … a_{k}cccx′y′. Then, the morphism h′ removes all occurrences of c, hence we get the string a_{1} … a_{k}x′y′ = x.

(⊇) Take a string x in the set in the right-hand side of the (∗). There are x_{1} ∈ L, x_{2} ∈ L, x_{3} ∈ R such that x is obtained as in (∗) from x_{1}, x_{2}, x_{3}. Denote:

x′_{1} = u_{1}cx′′_{1} ∈ L ⊔ ⊥ {c}, for x_{1} = u_{1}x′′_{1},
x′_{2} = h(u_{2})ch(x′′_{2}) ∈ h(L) ⊔ ⊥ {c}, for x_{2} = u_{2}x′′_{2},
x_{3} = a_{1}a′_{1} … a_{k}a′_{k}ccx′_{3}x′′_{3}, for k ≥ 0, x′_{3} ∈ V^{∗}, x′′_{3} ∈ V^{′∗}.

We must have a_{1}a′_{1} … a_{k}a′_{k} ∈ u_{1} ⊔ ⊥ h(u_{2}), hence u_{1} = u_{2} = a_{1} … a_{k}. Moreover, x′′_{1} = x′_{3} and h(x′′_{2}) = x′′_{3}. Consequently, x_{1} = ux′′_{1}, x_{2} = ux′′_{2}, for u = u_{1} = u_{2}, and x = ux′′_{1}x′′_{2} (by the definition of g and h′). But ux′′_{1}x′′_{2} ∈ C_{fp}(x_{1}, x_{2}) ⊆ C_{fp}(L).

According to the closure properties of F L, we get C_{fp}(L) ∈ F L (note that g is λ-free, h′ is limited, and that the closure under gsm mappings – even λ-free – implies the closure under the intersection with regular languages).

For the case of C_{mp} we replace the regular language R by:

R′ = {aa′ | a ∈ V }^{∗}{c^{2}}({bud′v | b, d ∈ V, u ∈ V^{∗}, v ∈ V^{′∗}, b ≠ d} ∪ V^{∗} ∪ V^{′∗}).

As above, we obtain:

C_{mp}(L) = h′(g(((L ⊔ ⊥ {c}) ⊔ ⊥ (h(L) ⊔ ⊥ {c})) ∩ R′).

The intersection with R′ forces the selection of strings a_{1}a′_{1} … a_{k}a′_{k}ccx′h(y′) as above, for a_{1} … a_{k}x′ ∈ L, a_{1} … a_{k}y′ ∈ L, with maximal k: either the next symbol (the first one in x′ and in y′) is different in the two strings, or one of x′, y′ is empty.

Therefore, C_{mp}(L) ∈ F L, too. ♢

Theorem 1. The families REG, CS, RE are closed under C_{α}, LIN and CF are not closed, α ∈ {fp, mp}.

Proof. The families in the Chomksy hierarchy have the closure properties in Lemmas 1, 2, but LIN, CF are not closed under intersection. ♢

4 Some Variants of the Basic Operations

In the definition above, either any common prefix or only the maximal prefix of two strings is considered when coordinating the strings. This might not cover the case when only certain prefixes can be accepted. This is modeled by the regulated prefix coordination operation, defined as follows.

For a regular language M ⊆ V^{∗} and x, y ∈ V^{∗}, we define:

C_{rp}(x, y) = {ux′y′ | x = ux′, y = uy′, for some u, x′, y′ ∈ V^{∗}, u ∈ M}.

(Only prefixes belonging to M are taken into consideration.)

Another natural variant is to coordinate substrings of the two strings, identifying both prefixes and suffixes of them. Formally, the free bilateral coordination of x, y ∈ V^{∗} is defined by:

C_{fb}(x, y) = {ux′y′v | x = ux′v, y = uy′v, for some u, v, x′, y′ ∈ V^{∗}}.

Because it is not clear how the maximal bilateral coordination should be defined, we do not consider here this case. (For instance, consider x = abbab, y = abbbab. The maximal common prefix is abb, the maximal common suffix is bbab; they overlap, both in x and in y!)

We can, however, define in the usual way the regulated bilateral coordination, asking that both u, v in the definition above are elements of a given regular language; we denote by C_{rb} this operation.

Both C_{fb}, C_{rb} can be extended in the natural way to languages.

The next step is to iterate the operations C_{α}, α ∈ {fp, mp, rp, fb, rb}, defining, for L ⊆ V^{∗}:

C_{α}^{∗}(L) = ⋃_{i≥0} C_{α}^{i}(L),

where

C_{α}^{0}(L) = L, C_{α}^{i+1}(L) = C_{α}(C_{α}^{i}(L)), i ≥ 0.

It is easy to see that Lemma 1 holds true with the same proof for all operations C_{α}, C_{α}^{∗}, α as above: with the notation in the proof of Lemma 1, we have:

C_{α}^{∗}(L) ∩ R = C_{α}(L) ∩ R, α ∈ {fp, mp, fb},

because the intersection with R selects the strings where only one occurrence of c is present. Moreover, for

R = M{cc_{1}c_{2}},

we also cover the case of α ∈ {rp, rb}.

Theorem 2. The families LIN, CF are closed under none of the operations C_{α}, C_{α}^{∗}, α ∈ {fp, mp, rp, fb, rb}.

Let us examine now the proof of Lemma 2.

Instead of transforming a prefix a_{1}a′_{1} … a_{k}a′_{k} of the scanned string into a_{1}a_{2} … a_{k}, the gsm g can also check whether or not a_{1}a_{2} … a_{k} ∈ M, for a given regular set. (Take a finite automaton for M and simulate it on the symbols a_{1}, …, a_{k}; the details are left to the reader.) Therefore, Lemma 2 holds true also for C_{rp}.

For the bilateral case, we modify the proof of Lemma 2 as follows:

– consider three new symbols c_{1}, c_{2}, c,

– instead of R, consider the regular set:

R′ = {aa′ | a ∈ V }^{∗}{c_{1}^{2}}V^{∗}V^{′∗}{c_{2}^{2}}{aa′ | a ∈ V }^{∗},

– instead of g, consider the gsm:

g′ = ({s_{0}, s_{1}, s_{2}, s_{3}, s_{4}}, V ∪ {c_{1}, c_{2}}, V ∪ {c}, s_{0}, {s_{4}}, δ′),

with the transition mapping defined as suggested by Figure 1.

Then, for L ⊆ V^{∗} we obtain:

C_{fb}(L) = h′(g′(((L ⊔ ⊥ {c_{1}c_{2}}) ⊔ ⊥ (h(L) ⊔ ⊥ {c_{1}c_{2}})) ∩ R′)).

If the coordination is regulated by a language M ∈ REG, then, as in the case of C_{rp}, we can modify g′ above in such a way to check whether or not the used prefix and suffix of the current strings are in M.

Consequently, Lemma 2 holds true also for C_{α}, α ∈ {fb, rb}.

Theorem 3. The families REG, CS, RE are closed under all operations C_{α}, α ∈ {fp, mp, rp, fb, rb}.

[figure: S_{0}; S_{1}; S_{3}; S_{4}; a/a; a/a; a/a; a′/a; a′/a; a′/a; c_{1}/c; c_{2}/c; c_{2}/c; Figure 1]

Theorem 4. The families CS, RE are closed under all operations C_{α}^{∗}, α ∈ {fp, mp, rp, fb, rb}.

Proof. For RE, the assertion is obvious (consequence of the Turing-Church Thesis). For CS, a straightforward (but long) construction can prove the assertion.

Here is the idea of such a construction for C_{fp}^{∗}. The modifications for the other cases are obvious:

– Start from a context-sensitive grammar G, for a language L ⊆ V^{∗};

– Generate a string x ∈ L(G);

– Generate one more string y ∈ L(G);

– Find a common prefix of x, y; let it be u (hence x = ux′, y = uy′);

– Having x, y, construct ux′y′;

– Consider ux′y′ in the role of x and go to step 2. It is clear that the grammar G′ obtained in this way generates exactly C_{fp}^{∗}(L).

Moreover, G′ has a bounded workspace: in order to generate a string w, it uses at most a space of length 2|w| (from x = ux′, y = uy′ we get w = ux′y′ and |xy| ≤ 2|ux′y′|). Consequently, L(G′) ∈ CS. ♢

The closure of REG under the operations C_{α}^{∗}, α ∈ {fp, mp, fb, rb}, remains open.

5 Syntactically Grounded Coordination

In the previous sections we have defined coordination operations on strings x, y without taking into account the syntactic structure of x, y. In natural languages, we pass from x = ux′, y = uy′ (or x = ux′v, y = uy′v) to w = ux′y′ (w = ux′y′v, respectively) only when u (u, v, respectively) has (have) the same syntactic structure. This makes necessary to consider the derivation trees of x, y, hence to define the coordination for trees, not for strings.

Take a context-free grammar G = (N, T, S, P).

Two derivation trees τ_{1}, τ_{2} with respect to G are said to be coordinable if there is a node ν_{1} in τ_{1} and a node ν_{2} in τ_{2} such that if we remove τ_{1}(ν_{1}) from τ_{1} and τ_{2}(ν_{2}) from τ_{2} and we label both ν_{1} and ν_{2} with the same symbol, then we obtain two identical trees.

For two coordinable trees τ_{1}, τ_{2} with respect to nodes ν_{1}, ν_{2} labelled by X, Y, respectively, we construct a tree τ_{3} as follows:

1. Excise τ_{1}(ν_{1}) from τ_{1}.

2. Label ν_{1} in the remaining tree by a new nonterminal symbol, Z.

3. Add at this node the subtree defined by the context-free rule Z → XY.

4. Attach τ_{1}(ν_{1}) to the new node labelled by X and τ_{2}(ν_{2}) to the new node labelled by Y.

The obtained tree, τ_{3}, has a terminal frontier.

If we have fr(τ_{1}) = u_{1}x_{1}v_{1}, fr(τ_{2}) = u_{2}x_{2}v_{2}, for x_{1} = fr(τ_{1}(ν_{1})), x_{2} = fr(τ_{2}(ν_{2})), then, because τ_{1}, τ_{2} are coordinable with respect to ν_{1}, ν_{2}, we have u_{1} = u_{2}, v_{1} = v_{2}. Then, fr(τ_{3}) = ux_{1}x_{2}v, for u = u_{1} = u_{2}, v = v_{1} = v_{2}.

Therefore, fr(τ_{3}) ∈ C_{fb}(fr(τ_{1}), fr(τ_{2})).

We say that τ_{3} has been obtained by coordination from τ_{1}, τ_{2}. For a grammar G, we denote by C(G) the language consisting of all strings fr(τ), for τ being a tree obtained by coordination from two derivation trees with respect to G.

Note that we define C(G) using exactly one coordination for each string in C(G).

Figure 2 presents the idea of coordinable trees and of coordination.

The fact that, when coordinating (the frontier of) trees, the common parts of the frontiers are not only equal but they also have the same syntactic description has a rather powerful (and somewhat surprising) influence on the result: the operation preserves context-freeness.

Theorem 5. For every context-free grammar G, the language C(G) is contextfree.

Proof. If G = (N, T, S, P), then we construct the grammar G′ = (N ∪ {Z}, T ∪ {c}, S, P′), with

P′ = P ∪ {A → xZy | A → xXy and A → xY y ∈ P,
for some x, y ∈ (N ∪ T)^{∗}, X, Y ∈ N}
∪ {Z → XcY | X, Y ∈ N}.

Consider also the regular set:

R = T^{∗}{c}T^{∗}

and the morphism h : (T ∪ {c})^{∗} → T^{∗} defined by h(a) = a, a ∈ T, and h(c) = λ. We obtain:

C(G) = h(L(G′) ∩ R).

[figure: ν_{2}; S; Y; v_{2}; u_{2}; τ_{2}(ν_{2}); x_{2}; τ_{2}; ν_{1}; S; X; v_{1}; u_{1}; τ_{1}(ν_{1}); x_{1}; τ_{1}; ⇓; Y; τ_{2}(ν_{2}); x_{2}; X; τ_{1}(ν_{1}); x_{1}; Z; S; v_{1} = v_{2}; u_{1} = u_{2}; τ_{3}; Figure 2]

Indeed, because when we coordinate two trees τ_{1}, τ_{2} of G with respect to two nodes ν_{1}, ν_{2} the trees obtained by excising τ_{1}(ν_{1}), τ_{2}(ν_{2}) from τ_{1}, τ_{2}, respectively, are identical modulo the labelling of ν_{1}, ν_{2}, there is a rule A → xXy used in τ_{1} and a rule A → xY y used in τ_{2} (possibly X = Y). Therefore, the new rules of P′ perform a coordination operation. Removing c by the morphism h, we get the result of coordination, hence C(G) ⊆ h(L(G′) ∩ R). Because the intersection with R selects from L(G′) exactly those strings in whose derivation we have used only once a rule Z → XcY, we have also the converse inclusion.

From the closure properties of CF we obtain C(G) ∈ CF. ♢ Corollary. If G is a regular grammar, then C(G) is also regular.

Proof. Exactly as above, starting from G regular, we construct G′. Because all recurrent derivations A ⟹^{∗} uAv in G′ have u ∈ T^{∗}, v = λ, according to Theorem 5.5 in Salomaa (1973), it follows that C(G) is a regular language. ♢

For linear grammar, the above results are not true.

Theorem 6. There is a linear grammar G such that C(G) ∉ LIN.

Proof. For the grammar:

G = ({S}, {a, b}, S, {S → aSb, S → ab}),

we clearly obtain:

C(G) = {a^{i}a^{n}b^{n}a^{m}b^{m}b^{i} | i ≥ 0, n, m ≥ 1},

which is not a linear language. ♢

In the coordination operation defined above, we allow not only to have both nodes ν_{1}, ν_{2} identically labelled, but it is also possible to have τ_{1}(ν_{1}) = τ_{2}(ν_{2}) (not to mention the weaker condition, fr(τ_{1}(ν_{1})) = fr(τ_{2}(ν_{2}))). Coordinating τ_{1} with τ_{1} looks artificial. Hence, we say that the coordination of τ_{1}, τ_{2} with respect to the nodes ν_{1}, ν_{2} is nontrivial if τ_{1}(ν_{1}) ≠ τ_{2}(ν_{2}). We denote by NC(G) the language consisting of all strings fr(τ), for τ being obtained by a nontrivial coordination of two derivation trees with respect to G.

The apparently small difference between usual tree coordination and nontrivial coordination turns out to have a surprising effect on the type of the language NC(G).

Theorem 7. There is a linear grammar G such that NC(G) ∉ CF.

Proof. Consider again the grammar G in the proof of Theorem 6. All derivations in G are of the form:

S ⟹ aSb ⟹ a^{2}Sb^{2} ⟹ … ⟹ a^{n}Sb^{n} ⟹ a^{n+1}b^{n+1}, n ≥ 0.

Thus, two subtrees of derivation trees with respect to G are different if they have different heights. Therefore, we have:

NC(G) = {a^{i}a^{n}b^{n}a^{m}b^{m}b^{i} | i ≥ 0, n, m ≥ 1, n ≠ m}.

Let us assume that NC(G) ∈ CF. Consider a context-free grammar G′ = (N, {a, b}, S, P) such that L(G′) = NC(G). In order to generate the prefix a^{i} and the suffix b^{i} in strings a^{i}a^{n}b^{n}a^{m}b^{m}b^{i} of NC(G), we need a derivation X ⟹^{∗} a^{j}Xb^{j}, j ≥ 1, X ∈ N. The rules used in such a derivation are not used when producing substrings a^{n}b^{n} or a^{m}b^{m}, because from X we have to generate substrings of the form a^{k}a^{n}b^{n}a^{m}b^{m}b^{l}. If in a subderivation leading to a block a^{n}b^{n} or a^{m}b^{m} of a string a^{i}a^{n}b^{n}a^{m}b^{m}b^{i}, after generating some a^{s}Y b^{s}, we introduce X from Y, then strings not in NC(G) will be obtained. Therefore, if we remove from P all rules contributing to a derivation X ⟹^{∗} a^{j}Xb^{j} as above, then we obtain a grammar G′′ generating strings of the form a^{i_{1}}a^{n}b^{n}a^{m}b^{m}b^{i_{2}}, for all n, m ≥ 1, n ≠ m, and with finitely many values for i_{1}, i_{2}. Because the pairs (i_{1}, i_{2}) are well specified and finitely many, we can replace by λ each occurrence of a and b in the rules of G′′ which contribute to the prefix a^{i_{1}} and to the suffix b^{i_{2}}, respectively. In this way, we obtain a context-free grammar G′′′ such that L(G′′′) = {a^{n}b^{n}a^{m}b^{m} | n, m ≥ 1, n ≠ m}.

However, L = {a^{n}b^{n}a^{m}b^{m} | n, m ≥ 1, n ≠ m} is not a context-free language. Assume the contrary. It follows that also L′ = {a^{n}b^{n}ca^{m}b^{m} | n, m ≥ 1, n ≠ m} is context-free. Take a context-free grammar G_{0} for L′. All recurrent derivations in G_{0} must be of the form X ⟹^{∗} a^{i}Xb^{i}, i ≥ 0. (Any other type of recurrent derivations produces strings not in a^{n}b^{n}a^{m}b^{m}, even without imposing restrictions on the relation between n and m.) Replace by λ each occurrence of b in G_{0}. The obtained grammar, G′_{0}, contain only recurrent derivations of the form X ⟹^{∗} a^{i}X, i ≥ 0. According to Theorem 5.5 in Salomaa (1973), the language L(G′_{0}) must be regular. However, L(G′_{0}) = h(L′), for h(a) = a, h(c) = c, h(b) = λ. Hence, L′(G′_{0}) = {a^{n}ca^{m} | n, m ≥ 1, n ≠ m}. This is not a regular language, a contradiction which concludes the proof. ♢

Theorem 8. There is a regular grammar G such that NC(G) ∉ REG.

Proof. Consider the grammar:

G = ({S}, {a, b}, S, {S → aS, S → b}).

We obtain:

NC(G) = {a^{i}a^{n}ba^{m}b | i ≥ 0, n, m ≥ 0, n ≠ m}.

As in the previous proof, if NC(G) is regular, then a regular grammar generating {a^{n}ba^{m}b | n, m ≥ 0, n ≠ m} can be constructed, which is contradictory, because this language is not regular. It follows that NC(G) ∉ REG, too. ♢

6 Central Coordination

The case of The boys eat apples + The girls eat bananas → The boys and the girls eat apples and bananas (respectively) suggests the following variants of coordination operations.

For x, y ∈ V^{∗}, we define the free central coordination by:

C_{fc}(x, y) = {x′y′ux′′y′′ | x = x′ux′′, y = y′uy′′, for some u, x′, x′′, y′, y′′ ∈ V^{∗}},

whereas the maximal central coordination is defined by:

C_{mc}(x, y) = {x′y′ux′′y′′ | x = x′ux′′, y = y′uy′′, for u, x′, x′′, y′, y′′ ∈ V^{∗},

and there is no proper superword of u which is common to x and y}.

The proof of Lemma 1 holds true also for C_{α}, C_{α}^{∗}, for α ∈ {fc, mc}, whereas the proof of Lemma 2 can be modified in order to cover the new operation (see also the remarks before Theorem 3). We get:

Theorem 9. The families REG, CS, RE are closed under C_{α}, CS, RE are closed under C_{α}^{∗}, too, but LIN, CF are closed under none of these operations, α ∈ {fc, mc}.

The central coordination can be naturally defined in the syntactically grounded variant, imposing that the substring u has the same syntactical description in both strings x, y.

We denote by C_{c}(G) the language of the frontier strings of trees obtained by central coordination of derivation trees in the context-free grammar G. Somewhat surprisingly, for this case we do not have a result like Theorem 4 above.

Theorem 10. There is a linear grammar G such that C_{c}(G) ∉ CF.

Proof. Consider the grammar:

G = ({S, A, B, C}, {a, b, c, d, e}, S, P),
P = {S → A, S → B, A → aAb, B → cBd, A → C, B → C, C → e}.

All strings of the form x = a^{n}eb^{n}, y = c^{m}ed^{m}, n, m ≥ 0, are in L(G) and they have the (maximal) common subword e. Moreover, in any derivation tree there is the subtree determined by C → e. Thus we have:

C_{c}(G) ∩ {a, c}^{∗}e{b, d}^{∗} = {a^{n}c^{m}eb^{n}d^{m} | n, m ≥ 0},

a language which is not context-free. ♢

One can easily see that for each regular grammar G we have C_{c}(G) ∈ REG: two derivation trees with respect to G can have in common only a subtree corresponding to a final part of the associated derivations, so the central coordination is, in fact, a “suffix coordination”.

7 Concluding Remarks

The following table synthesizes the results concerning the closure properties of families in the Chomsky hierarchy under the (non-iterated) coordination operations considered above (the notations are those used before, U stands for “undefined”)

C_{fp} C_{mp} C_{rp} C_{fb} C_{rb} C NC C_{fc} C_{mc} C_{c}
REG Yes Yes Yes Yes Yes Yes No Yes Yes Yes
LIN No No No No No No No No No No
CF  No No No No No Yes No No No No
CS  Yes Yes Yes Yes Yes U  U Yes Yes U
RE  Yes Yes Yes Yes Yes U  U Yes Yes U

Several interesting conclusions can be drawn on the basis of the results in this table.

With only one exception, that of unrestricted syntactically grounded coordination, none of these operations preserves the context-free languages.

Coordination is a basic linguistic operation, probably present in all languages. We have considered here many variants, both at the surface level of strings and taking into consideration derivation trees, hence the structure of strings. Thus, we can claim, at least statistically, that we have captured the idea of coordination by our definitions. Consequently, we can infer: natural languages contain non-context-free specific constructions. Coordination is one of them.

This does not necessarily implies that natural languages, English for instance, are not context-free languages in the restricted sense, as sets of strings, it merely means that natural languages contain constructions which cannot be handled by the context-free grammar formalism.

The only case when context-free languages are preserved, that of unrestricted syntactically grounded coordination, can be considered as insufficiently adequate, as it allows trivial coordination. Significantly enough, when nontrivial coordination is considered, the context-freeness is again lost. Moreover, there are linear grammars leading to non-context-free languages by nontrivial syntactically grounded coordination. (The fact that the family of linear languages is closed under none of the considered operations is not a surprise, because this family is not closed under concatenation while coordination involves a sort of concatenation in its definition.)

If context-free grammars are not sufficient, then what else ? This is not an easy question. The family of context-sensitive languages is closed under all coordination operations (except those syntactically grounded, which make no sense in this case as we have no available derivation tree). This confirms the general belief that natural languages lie somewhere at the context-sensitive level of the Chomsky hierarchy, but this is a loose conclusion: context-sensitive grammars are “too powerful”. A standard candidate are the Tree Adjoining Grammars (TAG), of various forms (with constraints, dependencies, etc). How the corresponding families of languages behave with respect to the previous coordination operations (on strings or on trees) remains as a research topic. The answer is of a definite interest for the adequacy of TAG’s as models of the syntax of natural language.

References

Chomsky, N. (1957). Syntactic structures. Mouton, The Hague.

Rozenberg, G. and A. Salomaa (Eds.) (1997). Handbook of formal languages. Springer-Verlag.

Sag, I., G. Gazdar, T. Wasow, and S. Weisler (1985). Coordination and how to distinguish categories. Natural Language and Linguistic Theory 3, 117–171.

Salomaa, A. (1973). Formal languages. Academic Press, New York.