Bericht Nr. 79, Oktober 1996

ISSN 0947-6954/96

Arbeitspapiere des Sonderforschungsbereichs 340

Sprachtheoretische Grundlagen für die Computer linguistik

Tom Cornell :

A Minimalist Grammar

for Deriving the Copy Language

Universität Stuttgart Universität Tübingen Deutschland Informationssysteme GmbH Arbeitspapiere des SFB 340

Bericht Nr. 79, Oktober 1996

A MINIMALIST GRAMMAR FOR DERIVING THE COPY LANGUAGE

TOM CORNELL

In these notes we present a minimalist derivational system modeled largely on Stabler’s formalization (Stabler 1996a,b) of (ideas from) Chomsky’s (1995) Minimalist Program. Our intention is to show that an extremely tightly constrained version of this system can nonetheless include grammars which generate the language

L_{ww} = {ww | w ∈ {0, 1}^{∗}}.

This language is known to be context-sensitive, and is the basis of the proofs in Huybregts (1984) and Shieber (1985) for the non-context-freeness of natural language. We focus here on an artificial language because it is possible to present a complete grammar which provably generates it. While the formalism is provably powerful enough to support grammars for (at least some) mildly context sensitive languages, it remains computationally attractive. In particular, its essentially linear use of lexical resources means that it should be decidable. This in turn may help to suggest ways to extend decidable grammar logics such as those presented in Rogers (1994) and Kracht (1995) beyond their current strictly contextfree power without losing decidability.

Our concern here is mainly to isolate what we hope is the minimal apparatus necessary to derive strings in L_{ww} in a Chomsky-style Merge & Move calculus. It turns out we will in fact need very little. As might be expected from the natural languages which exemplify L_{ww}-like behavior, we will only need head-movement. So, a fortiori, we will not need successive cyclic movement. This means we can stay within the “linear” fragment: every movement operation consumes some resources, and no operation increases resources. We will also need only one type of feature, namely categorial features (surely the minimal minimalist feature!)

ISSN 0947-6954/96 \begin{matrix}c \\ ◯ \end{matrix}1996 Der Autor

and their checking counterpart, selectional features. This means we will essentially be working in a categorial grammar with movement.

1. The Formalism

The formalism developed for Chomsky’s Minimalist Program in Stabler (1996a) is fundamentally derivational: the well-formed structures are the derivable structures. Following Chomsky (1995) we take derivations to start with a numeration, essentially a multiset of lexical items which constitutes a (minimally) structured database of resources from which we are to derive appropriate phrase markers. (Compare this approach to the logical approach to categorial grammars as in Moortgat (1996) and Kurtonina and Moortgat (1996), and refs.)

Derivations represent the application of two possible operations, Merge and Move, to the numeration. Move is constrained by the Last Resort principle, so that if it need not take place, it cannot take place. All movements are ultimately driven by the need to satisfy feature checking requirements. That is, features come in clashing pairs, and the object of the derivation is to place all features into a restricted set of configurations with clashing counterparts. In our fragment, we will be concerned to match category features with selection features, but we might equally well consider case-marking and case-assigning features, or nominal vs. predicative agreement features. In the linear fragment of this “derivational minimalism” we insist that clashing pairs of features leave us with a one-to-one and (almost) onto function from the categorial features to the selection features that cancel them. I say “almost” because one category (the category of the matrix clause) is not selected by anything else. So our derivations will be of structures containing only a single uncancelled category feature, which will be taken to be the category which the grammar assigns to the (well-formed) sound-meaning pair the derivation generates.

So, we think of a given feature abstractly as appearing either “positively charged” or “negatively charged”. In general, we distinguish attractor features from their clashing counterparts: movement will always be movement of an attracted feature (the attractand) into the checking domain of its attractor counterpart. For L_{ww}, selectional features will be the only attractor features we need.

Attractor features in general are distinguished in Chomsky’s work as being either weak or strong. Strength of a feature plays a role in the theory of movement. In Chomsky’s theory of movement, a derivation is divided into two stages—the overt componenet and the covert component—which

Category features Cat = {s, f, a, b}

Selection features Sel = \{\overline{ϕ} | ϕ ∈ Cat\}

Strong: \overline{F}, Weak: \overline{f}

Alphabet Σ = {0, 1}

Table 1. Primitive symbolic vocabulary of the formalism.

differ essentially in that movement operations in the overt component are constrained to “pied pipe” phonological (here orthographical) features. In the covert component, only the syntactic features themselves move. Strong features trigger movement in the overt component, weak features trigger movement in the covert component.

Stabler adopts a variant of this theory which dispenses with different components, distinguishing instead different kinds of movements. For our purposes we can think of this as just distinguishing what we might as well call “strong movement” from “weak movement”, where strong movement is movement which brings phonological features along with it while weak movement leaves them behind.^{1} We adopt here Stabler’s notational convention, presenting strong selection features in upper-case and the weak variant in lower-case. Note however that in L_{ww} all movements will be strong so the distinction is not used much here.

We will use the basic vocabulary of symbols and notation illustrated in Table 1. Given a category feature x, the corresponding selectional feature can be written either \overline{x} or \overline{X}. (We will use \overline{χ} to range over strong or weak variants of a feature \overline{x}.) Intuitively, the category s is the category of complete expressions, i.e., strings of the language being defined; f is a recursive functor category, roughly analogous to the V+Infl complex of natural languages, and a and b are “constant” categories, which themselves take no arguments, and which serve as the primary (nonrecursive) arguments of the f categories.

A lexicon is a set of trees; in L_{ww} all these trees will be simple atoms. These are illustrated in Table 2. Lexical items are written in the following notation. The formal features of a lexical item are written above the line, its associated interpretation-features (here just its orthographical features) are written below. We take the formal features to be ordered;

1Stabler’s system is in fact more complex than this, since there we must keep track of semantic features as well as phonological features. It appears that there are cases in which some, all or none of these interpretation-features are pied piped.

\frac{s,\overline{F}}{ϵ} (s) \frac{a}{0} (a) \frac{b}{1} (b)

\frac{f,\overline{F},\overline{a}}{0} (f_{a})

\frac{f,\overline{F},\overline{b}}{1} (f_{b})

\frac{f}{ϵ} (f_{0})

Table 2. The lexicon for L_{ww}.

this does not matter for any but the selectional features, and there we are just taking over the old assumption that we can distinguish internal and external arguments. However, this may be an innovation of Stabler’s, not present in Chomsky (1995). The symbols appearing in parentheses will be used as convenient names for the lexical items. (We cannot just use the orthographic forms, as the string “0”, for example, has two very distinct categories assigned to it.)

Note that for Chomsky all language variation is implemented in the lexicon. The definitions of Merge and Move are meant to be universal, so what trees we can derive depends only on what lexical material we have to start with. Therefore the lexicon in Table 2 is essentially what there is to our grammmar of L_{ww}. The main points to observe are that

• nothing selects s;

• f is always a complement, and

• f is only ever strongly selected—so f’s will always have to move, bringing their orthography with them;

• a and b are only ever weakly selected;

• the recursive f items always select for an a or b with the same orthographical features—this will implement a simple (and admittedly artificial) sort of “spec-head agreement”.

Strings of L_{ww} will be just those orthographic structures assigned the category s by the derivation system. The lexical items a and b are “constants”, that is, pure argument categories with no selectional features of their own. The lexical items f_{a} and f_{b} are the main functor/predicate elements. They are so named because f_{a} requires an a specifier and f_{b} requires a b specifier. Note also that items in the f category come in both recursive and nonrecursive varieties. The nonrecursive constant f_{0} provides the base of the recursion.^{2} So the well-formed syntactic structures, it will be shown, will all be of one general type: they will have an s-projection (“sP”) at the root, some number (maybe zero) of f_{a}P and f_{b}P in a strictly right-branching structure (with their associated aP and bP specifiers), with a single f_{0}P as the bottom-most phrase. Overt head movement will extract the f_{a} and f_{b} heads, moving them up under the root s head.

1.1. Trees. Syntactic phrase markers are just whatever structures our operations Merge and Move output, when we apply them (repeatedly) to the lexicon. However, despite the fact that there is no definition of what a phrase marker ought to look like outside of what is implicit in the definitions of Merge and Move, it is appropriate to consider explicitly what sort of structures we may look forward to.

Phrase markers are just trees in this formalism. Trees come in essentially two varieties: X^{0} and XP. Note however that these categories overlap somewhat. Every tree is headed by a unique X^{0} tree (the tree rooted in the node/segment called by Chomsky X^{0max}). The features of the head project up the tree according to an extremely simple rule of feature percolation:

all (and only) features of the head project.

(As far as I know this does not exclude orthographic features, though what use might be made of them outside X^{0} I cannot tell.)

Here we follow Stabler in using a notational convention which will serve to make these trees more readable. Interior nodes may bear labels from {<, >}. These are meant (following Stabler’s practice) to indicate down which branch the head of the tree is to be found. So, for example, the tree

\begin{aligned}& > \\ α & & β \end{aligned}

is headed by α, that is, it stands for the tree

\begin{aligned}& α \\ α & & β \end{aligned}

2There is no straightforward natural language analogue for f_{0}. We could have made the grammar of L_{ww} more natural, but at the cost of making proofs more complicated.

The tree

\begin{aligned}& < \\ α & & β \end{aligned}

on the other hand is headed by β and stands for the tree

\begin{aligned}& β \\ α & & β \end{aligned}.

Since we will be making extensive use of the head movement operation, we will be making extensive use of the adjunction structures which that operation creates. Normally, one handles adjunction by distinguishing between segments of a category (which correspond to nodes in the trees as they are customarily drawn) and the category itself, which is an unbroken chain of segments. The head of a tree is then that category which does not properly include any other category. However, in a system in which adjunction structures are created only by head movement and only serve to build up X^{0}’s, it is no longer clear whether the distinction we want is between categories and segments or between trees which are or are not X^{0}(word-internal/-external domains). That is, the key piece of information we have to recover from a tree is, for whatever reason, the identity of the node (X^{0max}) where the X^{0} proper leaves off and the rest of the structure begins. Whether the nodes which appear “south of the border” are categories or segments of categories is immaterial for our purposes. We will therefore adopt the following convention: interior nodes which belong to X^{0} will be labeled with ‘∘’ rather than ‘>’ or ‘<’. Since head adjunction structures are uniformly left-headed here, no information is lost thereby. (We can think of ‘∘’ as a segment-level or head-internal analog of ‘>’.) So the structure

\begin{matrix}> \\ \begin{aligned}& ∘ \\ α & & β \end{aligned} & γ \end{matrix}

is meant to represent a tree whose head is the complex X^{0}

\begin{aligned}& ∘ \\ α & & β \end{aligned}

to which γ has been attached as a complement. Note that the issue of X^{0}-internal headedness is far from clear-cut. Since heads adjoined into another head have their features visible to categories outside the complex X^{0} so formed, it does not seem that in this case the features of the head are accurately described as “projecting over” the features of its adjuncts. However, we will assume that head adjunction has fixed consequences for the order in which the combined orthographical strings appear. For our own purposes we will assume that adjuncts all appear to the right of the material to which they are adjoined. This is necessary to derive the copy language with head movement, and reflects the apparent facts of Dutch and Swiss German, for example, though not of all headadjunction phenomena. Note however that we could reverse the order; in that case, we would derive not the copy language but the palindrome language. While the latter language is known to be context free, that is, it is derivable from a recognizable set of trees, in our case we would still be assigning to its strings trees from a nonrecognizable set. The power of the system is not thereby compromised, but it is harder to see.

2. Feature Checking

The essential intuition developed in Chomsky (1995) is that all movement is driven by the need to satisfy the demands of feature checking. In our particular examples, we will consider that heads marked with selection features will need to find, in their checking domain, a head with a corresponding categorial feature. So for example if α is a head with selection feature \overline{b}, then that feature must be checked against some head of category b in α’s domain. The acceptable structures will then be those in which all features needing to be checked (the selection features) have been cancelled against appropriately situated opposite-polarity versions of the same feature. Again, we will restrict ourselves here to the linear fragment, in which in addition all but one category feature must cancel a unique selection feature, leaving one remaining uncancelled feature, the category of the matrix.

The domain of feature checking is essentially two-fold in our system: specifiers of a phrase and adjuncts of a head are in the checking domain of the local head. For Chomsky, the checking domain of an unmoved head is essentially the set of categories attached to its projection, excluding the complement. Note that head movement extends the domain of the moved head. For our purposes this means that any unchecked features of a moved head can be checked in the domain of its landing site. Put another way, a given X^{0} can be considered to have as features the union of the (unchecked) features of its constituents. (Though in fact none of our examples will afford an instance of this feature pied-piping.)

For example, in the tree

\begin{aligned}& < \\ \frac{a}{0} & >_{\frac{f,\overline{a}}{0}} \end{aligned}

the pair of clashing features ⟨a, \overline{a}⟩ stand in a checking configuration (in particular \frac{a}{0} is attached to a projection of \frac{f,\overline{a}}{0} and is not its complement). So they can be cancelled against each other. On the other hand, in the tree

\begin{aligned}& > \\ \frac{f,\overline{F}}{1} & \begin{aligned}& < \\ \frac{∅}{0} & >_{\frac{f}{0}} \end{aligned} \end{aligned}

the pair ⟨f, \overline{F}⟩, where the first member is the category feature of the lower head, do not stand in a checking relation. In such a configuration we could raise the head of the complement to adjoin to the head of the overall tree, yielding

\begin{aligned}& > \\ ∘_{\frac{f,\overline{F}}{1} \frac{f}{0}} & & \begin{aligned}& < \\ \frac{∅}{0} & >_{\frac{∅}{ϵ}} \end{aligned} \end{aligned}

In this tree, the downstairs head \frac{f}{0} is now in the checking domain of the upstairs head \frac{f,\overline{F}}{1} so we can cancel them.

3. Operations

There are two basic operations in Chomsky’s calculus: Merge and Move. Here we will distinguish two sorts of Move: strong Move and weak Move. Note that, in standard linguistic terms, all the instances of Move we will consider here could be construed as instances of Head (X^{0}) Movement.

3.1. Merge. In both Chomsky’s and Stabler’s systems Merge is essentially free. It may result in checking of features, but it need not. In Stabler’s resource-oriented terms, Merge does not necessarily consume any resources.^{3} However, it is still sensitive to syntactic features in the following sense. Merge is a two-place operation which takes two trees as arguments, one of which selects the other.

Definition 1. A tree t_{1} selects another tree t_{2} if the head of t_{1} has as its first selectional feature \overline{x} or \overline{X} and the head of t_{2} contains a corresponding categorial feature x. We refer to x as the active selection feature. We refer to t_{1} as the selecting tree and t_{2} as the selected tree.

Definition 2. A tree t is selectionally inert if it contains no uncancelled selection features.

Merge is directional in a sense familiar from GB theory: an X^{0} takes its complement to the right and its specifier to the left. In our terms, if the root of the selecting tree is < or > then it becomes the right-hand subtree after merger; otherwise it becomes the left-hand subtree. The resulting tree is labeled < in the former case, > in the latter case; that is, the selecting tree becomes the head of the resulting construction.

So, for example:

(1)  Merge(\frac{f,\overline{a}}{0}, \frac{a}{0}) = >_{\frac{f,\overline{a}}{0}  \frac{a}{0}}

On the other hand,

(2) Merge(\begin{matrix}& > \\ \frac{f,\overline{a}}{0} & & t \end{matrix} , \frac{a}{0}) = \begin{aligned}& < \\ \frac{a}{0} & \begin{aligned}& > \\ \frac{f,\overline{a}}{0} & & t \end{aligned} \end{aligned} Definition 3. Given a pair of trees t_{1}, t_{2}, such that t_{1} selects t_{2}, t_{2} selectionally inert. Then

3Note that this is obvious only in Stabler’s earliest grammars. Later Merge and Move (for heads) are combined into a single operation, which does consume features, presumably as a consequence of the movement component of the operation.

(3) Merge : (t_{1}, t_{2}) ↦ \begin{cases}\begin{aligned}& > \\ t_{1} & & t_{2} \end{aligned} & if t_{1} is X^{0}, \\ \begin{aligned}& < \\ t_{2} & & t_{1} \end{aligned} & if t_{1} is not X^{0}. \end{cases}

Note that adjunction structures are never created by Merge in this system. (So, in particular, the action of Merge on two X^{0}’s is determinate.)

Observe also the following. Suppose we have a head \frac{f,\overline{F},\overline{a}}{0}, that is, a transitive head. Since Merge is constrained by the current value of the leftmost selection feature (\overline{F} in this case), it will not be possible to merge in a tree of category \frac{a}{0} until the \overline{F} feature has been cancelled. This is a very strong condition which forces the derivation to develop along very narrowly constrained lines. I do not know if it is absolutely necessary, but it will certainly make proofs of grammar-language correspondence easier, so I will retain it here. (It comes originally from Stabler (1996a).)

3.2. Move. Move as defined here is just head movement. The essential idea is as usual: applying Move to a tree has the effect of detaching some subtree of the input, and then combining it again with the tree from which it has been detached, but now in another position. Following the general bent of the minimalist program, we treat movement as driven by the attraction of a categorial feature by a selection feature, where the attracted categorial feature pied-pipes its orthography if it is strongly attracted, not if weakly.

Normally, head movement is treated as a species of adjunction, and supposed thereby to be just like any other kind of movement. However, by the time Chomsky is finished with chapter 4 of The Minimalist Program, it would appear that this is the only species of adjunction left in the grammar, so in fact head movement is not just like any other sort of movement. So “head movement” and “adjunction” will be synonymous for the remainder of this paper. This leaves us with four kinds of movement: strong XP movement, weak XP movement, strong X^{0} movement and weak X^{0} movement. Of these only strong X^{0} movement is exemplified in the derivation of strings in L_{ww}.

We stipulate here that all movement is upward. That is, given a node including a selection feature, it can only look into its sister to find something to attract. So we define a head t_{2} as being accessible to another head t_{1} just in case it is a subtree of the sister of t_{1} (that is, t_{1} i-commands t_{2}). Obviously, for constructing reasonable facsimiles of natural language, more complex notions of accessibility may be entertained. We introduce the concept here so as to retain a hook accessible [sic] for later extensions and elaborations.

Normally Move is subjected to some sort of locality condition. Here it appears we can get by with the optimally simple condition: move only the closest tree whose head you attract. That is, if the attractor feature is \overline{χ}, then the closest attractand is a tree marked x such that no other x-tree c-commands it. Note that if there is no closest such tree (there is more than one equidistant tree, or there are no such trees at all) then Move is undefined. Again, like accessibility this notion of nearness is too trivial to stand up for long against the tidal pull of linguistic data, but it suffices for L_{ww}, and it gives us a convenient hook accessible for later work.

Definition 4. A tree t_{1} attracts another tree t_{2} if there is some selection feature \overline{χ} ∈ cat(t_{1}) such that x ∈ cat(t_{2}). (Where χ ranges over x and X.)

Let t_{1}/t_{2} denote the result of removing t_{2} from t_{1}. A little more formally, suppose we have a collection of special labels (call them variables) (\frac{∅}{ϵ})_{x} and (\frac{∅}{w} )_{x}, with indices drawn from some index set X. Then, given some x ∈ X, t_{1}/_{x}t_{2} is that tree such that replacing every occurrence of a variable indexed by x with t_{2} would yield t_{1}. We will refer to this division operation as detachment, distinguishing weak detachment (in which t_{2} corresponds to a “variable” of the form (\frac{∅}{w} )_{x}) from strong detachment (in which t_{2} corresponds to a variable of the form (\frac{∅}{ϵ})_{x}). We limit detachment to heads, and insist that weak detachment remove all features from a given position and leave behind all the orthography associated with that position.

So, weak movement will be weak detachment of the nearest attracted head followed by adjunction to the head of the whole tree, and strong movement will be strong detachment of a head followed by adjunction to the head of the whole tree. Weak movement is triggered by a weak attractor feature in the tree’s head, while strong movement is triggered by a strong attractor feature in the tree’s head. Note that there is in practice no need to keep the “variable”-tag in the vacated “trace” position. In this system we need neither indices, chains nor traces. (These annotations could be required again if we wanted to build a logical calculus around the algebraic calculations we are employing here.)

Definition 5. Given trees

t_{1} = \frac{\{\overline{χ}\} ∪ G}{v}

and

t_{2} = \frac{\{χ\} ∪ H}{w}

and a tree

t = \begin{aligned}& > \\ t_{1} & & t′[t_{2}] \end{aligned}

and in particular t_{2} is that subtree which is closest to t_{1} among those heads marked {χ}. Then

Move(t) = \begin{aligned}& > \\ ∘_{\frac{G}{v} \frac{H}{w}} & & t′/t_{2} \end{aligned}

In this definition, we present feature cancellation as actually being part of the Move operation. In fact, Move as we have defined it invariably feeds feature cancellation. In this way we have built the Last Resort Principle into the definition of the Move operation, with the effect that Move only applies if their is no other way for the derivation to proceed. Since the derivation is always driven by the need to cancel features, this means that Move will in principle only apply if it can lead to feature cancellation. But whether that feature cancellation is actually a built-in sub-operation of Move or a separate operation which Move feeds is not really determined by the ideas laid out in Chomsky (1995).

4. A Derivation of the String 1010

In this section we present and describe the derivation in our formalism of the string 1010. We present it as a derivation tree (a T-marker, to revive Chomsky’s old terminology), though, spread out as it is over a number of pages, the overall structure of this meta-tree may be less than transparent. The T-marker is constructed deliberately to resemble a proof tree, but bear in mind we are only tracing algebraic calculations here, not (yet!) doing proofs in a logic.

Definition 6. A χ-tree is a tree containing χ as its only uncancelled feature.

\frac{f,\overline{F},\overline{a}}{0} \frac{f}{ϵ} ; >_{\frac{f,\overline{F},\overline{a}}{0}  \frac{f}{ϵ}} (Merge)

\begin{matrix}> \\ ∘_{\frac{f,\overline{F},\overline{a}}{0} \frac{f}{ϵ}} & \frac{∅}{ϵ} \end{matrix} (Move)

\begin{matrix}> \\ ∘_{\frac{f,\overline{a}}{0} \frac{∅}{ϵ}} & ϵ \end{matrix} (Cancel)

Figure 1. Complement selection and subsequent X^{0} movement.

Our goal will be to derive an s-tree. In fact we will later define the language generated by our grammar to be just those strings which are the yields of s-trees.

The numeration we begin from is as follows.

(4) \frac{s,\overline{F}}{ϵ}, \frac{b}{1}, \frac{f,\overline{F},\overline{b}}{1}, \frac{a}{0}, \frac{f,\overline{F},\overline{a}}{0}, \frac{f}{ϵ}

Using our abbreviated notation, this becomes the following.

(5) s, b, f_{b}, a, f_{a}, f_{0}

Our first move cannot be a Move, since the numeration contains only atoms, so it must be a Merge. Furthermore, to be a legal application of Merge, it must combine a functor category which selects an inert (nonfunctor) category. All three functor categories select for f, and the only selectionally inert element of that category is f_{0}, so it must be the second argument to Merge. We can begin with any of the three functor categories as the first argument to Merge. Note that if we choose s, it will trigger the raising of f_{0}, cancelling all uncancelled features but the s, ending the derivation with an s-tree which yields the empty string, which is an element of L_{ww} (though not derivable from the full numeration in (4)). However, we will avoid this trivial option and choose to apply Merge to f_{a} and f_{0}.

Figure 1 shows this first step and the subsequent raising of f_{0} to adjoin to f_{a}. Note that here we have illustrated feature cancellation as a separate step; this is done for clarity of the presentation and not out of principle. Recall that we have in fact defined head movement as involving feature cancellation.

Note that when we first empty out the content of a given position (either by Move, Cancel or both), we will leave a syntactically empty symbol in the relevant position, but after that we will retain only the orthography associated with each position. Note that structure dominating only the empty string could be simply removed at this point, “garbage-collected away,” so to speak. Items with no syntactic features will play no role in the remaining derivation.

\begin{matrix}> \\ ∘_{\frac{f,\overline{a}}{0} \frac{∅}{ϵ}} & ϵ \end{matrix} \frac{a}{0} ; \begin{aligned}& < \\ \frac{a}{0} & \begin{matrix}> \\ \begin{aligned}& ∘ \\ \frac{f,\overline{a}}{0} & & ϵ \end{aligned} & ϵ \end{matrix} \end{aligned} (Merge) ; \begin{aligned}& < \\ \frac{∅}{0} & \begin{matrix}> \\ \begin{aligned}& ∘ \\ \frac{f}{0} & & ϵ \end{aligned} & ϵ \end{matrix} \end{aligned} ; (Cancel)

Figure 2. Specifier selection, spec/head configuration.

Once head movement has led to the cancellation of the \overline{F} feature, the next selection feature (\overline{a}) is exposed, and we are allowed to Merge in the a from our numeration. Note that no other operation is possible: the \overline{a} feature cannot be satisfied by Move, in particular, and nothing else is allowed to Merge.

\frac{f,\overline{F},\overline{b}}{1} \begin{aligned}& < \\ \frac{∅}{0} & \begin{matrix}> \\ \begin{aligned}& ∘ \\ \frac{f}{0} & & ϵ \end{aligned} & ϵ \end{matrix} \end{aligned}

\begin{aligned}& > \\ \frac{f,\overline{F},\overline{b}}{1} & \begin{aligned}& < \\ 0 & \begin{matrix}> \\ \begin{aligned}& ∘ \\ \frac{f}{0} & & ϵ \end{aligned} & ϵ \end{matrix} \end{aligned} \end{aligned}

(Merge)

\begin{matrix}> \\ \begin{aligned}& ∘ \\ \frac{f,\overline{b}}{1} & & \begin{aligned}& ∘ \\ \frac{∅}{0} & & ϵ \end{aligned} \end{aligned} & \begin{aligned}& < \\ 0 & \begin{aligned}& > \\ \frac{∅}{ϵ} & & ϵ \end{aligned} \end{aligned} \end{matrix} (Move/Cancel)

\frac{b}{1}

\begin{aligned}& < \\ \frac{∅}{1} & \begin{matrix}> \\ \begin{aligned}& ∘ \\ \frac{f}{1} & \begin{aligned}& ∘ \\ 0 & & ϵ \end{aligned} \end{aligned} & \begin{aligned}& < \\ 0 & \begin{aligned}& > \\ ϵ & & ϵ \end{aligned} \end{aligned} \end{matrix} \end{aligned}

(Merge/Cancel)

Figure 3. Raising a complex head.

Once we attach the a specifier and cancel the a feature we have derived an f-tree, a tree in which f is the only “live” feature. This tree is illustrated as the last step of Figure 2 (also the first step of Figure 3). Again, we could merge this with s, effectively completing the derivation. After the raising of the downstairs head, we would derive an s-tree yielding the string 00, also a member of L_{ww}. But as before we continue by merging in another f-head, this time f_{b}.

\frac{s,\overline{F}}{ϵ} \begin{aligned}& < \\ \frac{∅}{1} & \begin{matrix}> \\ \begin{aligned}& ∘ \\ \frac{f}{1} & \begin{aligned}& ∘ \\ 0 & & ϵ \end{aligned} \end{aligned} & \begin{aligned}& < \\ 0 & \begin{aligned}& > \\ ϵ & & ϵ \end{aligned} \end{aligned} \end{matrix} \end{aligned} ; \begin{aligned}& > \\ \frac{s,\overline{F}}{ϵ} & \begin{aligned}& < \\ 1 & \begin{matrix}> \\ \begin{aligned}& ∘ \\ \frac{f}{1} & \begin{aligned}& ∘ \\ 0 & & ϵ \end{aligned} \end{aligned} & \begin{aligned}& < \\ 0 & \begin{aligned}& > \\ ϵ & & ϵ \end{aligned} \end{aligned} \end{matrix} \end{aligned} \end{aligned} (Merge) ; \begin{matrix}> \\ \begin{aligned}& ∘ \\ \frac{s}{ϵ} & \begin{aligned}& ∘ \\ \frac{∅}{1} & \begin{aligned}& ∘ \\ 0 & & ϵ \end{aligned} \end{aligned} \end{aligned} & \begin{aligned}& < \\ 1 & \begin{aligned}& > \\ \frac{∅}{ϵ} & \begin{aligned}& < \\ 0 & \begin{aligned}& > \\ ϵ & & ϵ \end{aligned} \end{aligned} \end{aligned} \end{aligned} \end{matrix} ; (Move/Cancel)

Figure 4. Final steps.

This leads to the raising of the complex head, canceling the \overline{F} feature and exposing the \overline{b} feature. Merging in a b specifier leaves us with yet another f-tree, the last step in the sub-derivation in Figure 3.

This time we do cap off the derivation by merging in our s. This triggers raising of the complex head and, after feature cancelation, the derivation of an s-tree is complete. As required, it yields the string 1010.

5. All and Only L_{ww}

It should be clear that we can derive any string in L_{ww} with this system. Abstractly, what we are doing is creating a purely right-branching “main” tree, which, again abstracting away from the timing of our derivation steps, represents a string with strictly serial dependencies, consisting of pairs of 0’s and 1’s. Then head movement strips out the lower members of each of these pairs, constructing a parallel “head” tree which preserves the order of the original tree. So, roughly, from underlying [[11][00]] we derive [[10][10]] by separating all the heads from all the specifiers.

Proposition 1. For any string in the {0, 1}^{∗} copy language, there is an s-tree which yields it.

That we derive only strings in L_{ww} is less clear, and we take some time to prove this in this section. We state the theorem now, and then develop the proof in several steps.

Theorem 1. Every s-tree yields a string from the {0, 1}^{∗} copy language.

We begin with a simple observation about f-trees: every (finite!) f-tree must contain at its base an instance of \frac{f}{ϵ} (or, more accurately, a position from which an instance of \frac{f}{ϵ} was removed by movement). This is a direct consequence of the recursive structure of the f-categories.

Lemma 1. For all categorial features other than s, the numeration must contain an equal number of clashing selection features, and vice-versa.

This is guaranteed by the linearity of our operations: outside of s, we must establish a bijection between categorial and selection features, so the sets involved must be of the same size.

Lemma 2. There can be exactly one instance each of \frac{s,\overline{F}}{ϵ} and \frac{f}{ϵ} in any derivation of an s-tree.

Note first that nothing selects s, so by the definition of an s-tree it can only have a single \frac{s,\overline{F}}{ϵ} in it. Next note that this one \frac{s,\overline{F}}{ϵ} atom that we need to derive an s-tree itself selects \overline{F}. So, by Lemma 1, there must be something in the derivation which introduces a corresponding f feature. All the recursive f-categories introduce an f category feature, but also another \overline{F} feature. So only an instance of nonrecursive \frac{f}{ϵ} can balance out the \overline{F} feature introduced by \frac{s,\overline{F}}{ϵ}. So we must have at least one \frac{f}{ϵ} in our derivation.

The argument works the other way as well. Suppose we have an \frac{f}{ϵ} in our derivation. It introduces an f category feature which must be balanced against an \overline{F} (or \overline{f}) selection feature. But once again the recursive f atoms introduce their own f features for each \overline{F} that they introduce. So only an \frac{s,\overline{F}}{ϵ} can balance the f feature introduced by an \frac{f}{ϵ}. Since \frac{s,\overline{F}}{ϵ} is unique, \frac{f}{ϵ} must be as well. □

Now consider what must happen for us to derive an s-tree. Obviously, we will have to Merge an instance of \frac{s,\overline{F}}{ϵ} with an appropriate complement. That hypothetical complement will have to be an f-tree, by the definition of Merge applied to the lexical item \frac{s,\overline{F}}{ϵ}. Suppose that this f-tree yields the string uvw, where v is the part of the string dominated by the X^{0max}. Then the derivation of an s-tree must proceed as follows.

\frac{s,\overline{F}}{ϵ} ⟶_{Merge} >_{\frac{s,\overline{F}}{ϵ} (\frac{f}{uvw} )} ⟶_{Move} \begin{matrix}> \\ ∘_{\frac{s}{ϵ} (\frac{∅}{v})} & (\frac{∅}{uw} ) \end{matrix} (6)

Note that there is one alternative possibility in this derivation. Since Merge does not use up the selection feature \overline{F}, it would be possible to apply Merge yet again, merging another inert f-tree as specifier. In fact, you could do this as many times as you liked. However, doing it even once is too much: every f-tree contains an instance of \frac{f}{ϵ}, and we know already from Lemma 2 that we can only have one of these in a derivation, and we already have one in the complement.

So now we see what we need to prove to establish Theorem 1.

Lemma 3. Every f-tree yields a string of the form uvw, where the X^{0max} yields v, and v = uw.

The base is trivial: \frac{f}{ϵ} dominates the empty string.

For the inductive step we use the same “partial evaluation” technique that we used above. Suppose for concreteness that we are building an f-tree with \frac{f,\overline{F},\overline{a}}{0} as its head. Again, the first thing we must do is to merge \frac{f,\overline{F},\overline{a}}{0} with an appropriate complement, namely another f-tree.

\frac{f,\overline{F},\overline{a}}{0} ⟶_{Merge} >_{\frac{f,\overline{F},\overline{a}}{0} (\frac{f}{uvw} )}

(7)

By the inductive hypothesis, this tree yields a string of the form uvw, where v is the substring dominated by the head, and it equals uw.

Again, note that we could consider merging another f-tree as specifier, but that would introduce too many \frac{f}{ϵ}’s into the derivation, as we have already observed. So we must move, to cancel the \overline{F} feature, before the derivation can proceed any further.

(8)  \frac{f,\overline{F},\overline{a}}{0} ⟶_{Merge} >_{\frac{f,\overline{F},\overline{a}}{0} (\frac{f}{uvw} )}

⟶_{Move} \begin{matrix}> \\ ∘_{\frac{f,\overline{a}}{0} (\frac{∅}{v})} & (\frac{∅}{uw} ) \end{matrix} (9)

⟶_{Merge} \begin{aligned}& < \\ (\frac{∅}{0}) & \begin{matrix}> \\ ∘_{\frac{f}{0} (\frac{∅}{v})} & (\frac{∅}{uw} ) \end{matrix} \end{aligned} (10)

Once we have cancelled the \overline{F} feature we can consider how to cancel the \overline{a} feature. Theoretically, we could now move an a-tree from within the complement, but since, by assumption, the complement is an f-tree, there can be no such a-tree within it: it contains no live features other than f. Note that we cannot merge more than one a-tree here, since we use up the \overline{a} feature of the head as soon as we Merge an a-category into its checking domain. So we merge exactly one \frac{a}{0}, and we are done: we have derived a new f-tree in the only way possible. Checking that our inductive hypothesis is verified, we note that our f-tree dominates a string of the form u′v′w′, where u′ = 0, v′ = 0v, and w′ = uw. So we have to show that

v = uw ⇒ 0v = 0uw (11)

which is obvious. □

Theorem 1 now follows immediately, given (6).

References

Chomsky, N. (1995). The Minimalist Program, MIT Press. Huybregts, R. (1984). The weak inadequacy of context-free phrase struc-

ture grammars, in de Haan, Trommelen and Zonneveld (eds), Van Periferie naar Kern, Foris, Dordrecht, pp. 81–99.

Kracht, M. (1995). Syntactic codes and grammar refinement, Journal of

Logic, Language, and Information 4: 41–60. Kurtonina, N. and Moortgat, M. (1996). Structural control, in P. Black-

burn and M. de Rijke (eds), Specifying Syntactic Structures, CSLI Publications, Stanford, CA.

Moortgat, M. (1996). In situ binding: A modal analysis, in Dekker and Stokhof (eds), Proceedings 10th Amsterdam Colloquium, ILLC, Amsterdam, pp. 539–549.

Rogers, J. (1994). Studies in the Logic of Trees with Applications to Grammar Formalisms, PhD thesis, University of Delaware, Department of Computer & Information Sciences.

Shieber, S. M. (1985). Evidence against the context-freeness of natural

language, Linguistics and Philosophy 8: 333–343. Stabler, E. P. (1996a). Acquiring and parsing languages with

movement, Basil Blackwell, Oxford. (Drafts available at http://128.97.8.34/utrecht/utrecht.html.).

Stabler, E. P. (1996b). Computing quantifier scope, in A. Szabolcsi (ed.), Ways of Scope Taking, Kluwer, Boston.

Seminar für Sprachwissenschaft, University of Tübingen

E-mail address: cornell@sfs.nphil.uni-tuebingen.de