A logical treatment of semi-free word order and bounded discontinuous 
constituency 
Mike Reape 
Centre for Cognitive Science, University of Edinburgh 
2 Buccleuch Place, Edinburgh EH8 9LW 
Scotland, UK 
Abstract 
In this paper we present a logical treatment of semi- 
free word order and bounded discontinuous 
constituency. We extend standard feature value 
logics to treat word order in a single formalism with 
a rigorous semantics without phrase structure rules. 
The elimination of phrase structure rules allows a 
natural generalisation of the approach to 
nonconfigurational word order and bounded 
discontinuous continuency via sequence union. 
Sequence union formalises the notions of clause 
union and scrambling by providing a mechanism for 
describing word order domains larger than the local 
tree. The formalism incorporates the distinction 
between bounded and unbounded forms of 
discontinuous constituency. Grammars are 
organised as algebraic theories. This means that 
linguistic generalisations are stated as axioms about 
the structure of signs. This permits a natural 
interpretation of implicational universals in terms of 
theories, subtheories and implicational axioms. The 
accompanying linguistic analysis is eclectic, 
borrowing insights from many current linguistic 
theories. 
1. Introduction 
In this paper we present a logical treatment of semi- 
free word order and bounded discontinuous 
constituency. By a logical treatment, we mean that 
the grammar is an axiomatic algebraic theory, i.e., a 
set of axioms formalised in a logic. By bounded 
discontinuous constituency, we refer to phenomena 
such as Dutch cross-serial dependencies, German 
Mittelfeld word order and clause-bounded 
extraposition in contrast to unbounded forms of 
discontinuous constituency such as cross-serial 
multiple extractions in Swedish relative clauses. 
There is no scope within this paper to provide the 
linguistic argumentation sufficient to justify the 
approach described below. We shall have to limit 
ourselves to describing the key linguistic insight that 
we wish to formalise. That is that semi-free word 
order and nonconfigurationality are local 
phenomenon (i.e., bounded) and that word order 
domains are larger than the local trees of context- 
free based accounts of syntax. (This includes nearly 
all well-known unification-based grammar 
formalisms such as GPSG, IF'G, I-IPSG and CUG.) This is 
simply a restatement of the notion of clause union or 
scrambling familiar from transformational analyses. 
Our proposal is to provide a feature-value logic with 
a rigorous semantics with sufficient expressive 
power to allow the encoding of even syntactic 
structure within the single formalism. This means 
that the work of encoding syntactic structure is 
carried by the feature-value logic and not by formal 
language theoretic devices (i.e., phrase structure 
rules). Sequences of linguistic categories, or signs 
(following Saussure, HI~G and UCG), do the work of 
PSRs in our logic. The phon attribute of signs is 
functionally dependent on the phon attributes of 
the signs in sequences encoding local order 
domains. This allows us to trivially introduce word 
order domains larger than the local tree by 
introducing a sequence union operation. GPSG-style 
linear precedence (LP) statements express partial 
ordering constraints on elements of sequences. 
The grammars we use consist of three types of 
elements: (1) descriptions of lexical signs, (2) 
descriptions of nonlexical signs and (3) axioms 
which specify the redundant structure of signs. This 
organisation is similar to that of HPSG (Pollard and 
Sag, 1987) from which we borrow many ideas. 
Subcategorisation is expressed in terms of sets of 
arguments. This borrows ideas from all of HPSG, LFG 
(Bresnan, 1982) and categorial grammar (CC). 
However, like HPSG and unlike LFG, our set 
descriptions are collapsible. We also share with CG 
the notions that linguistic structure is based on 
functor-argument structure and that lexical functors 
partially order their arguments. 
All word order facts are captured in the way that 
lexical functors combine the ordering domains (dtrs 
sequences) of their arguments. Functors can 
combine order domains in one of two ways. They 
can take the sequence union of two sequences or 
concatenate one with the other. Discontinuity is 
achieved via sequence union. Continuity is 
achieved via concatenation. Since functors partially 
order sequences by LP statements, order amongst 
both continuous and discontinuous constituents is 
treated in the same way. This solves the problem 
often noted in the past of specifying the appropriate 
~.-~ - 103- 
constituents as sisters so that LP statements can 
apply correctly while satisfying the 
subcategorisation requirements of lexical heads and 
coindexing constituents correctly with 
subcategorised arguments. Furthermore, order is 
"inherited" from the "bottom" since sequence 
union preserves the relative order of the elements of 
its operands. The empirically falsifiable linguistic 
hypothesis made is that the whole range of local 
word order phenomena is treatable in this way. 
In §2 we present the syntax and semantics of the 
feature-value logic In §3 we develop a methodology 
for organising grammars as algebraic theories. In ~4 
we present a toy analysis of Dutch subordinate 
clauses which illustrates the basic ideas underlying 
this paper. We very briefly discuss an 
interpretation of parametric variation in terms of 
theories and subtheories in §5 and possible 
implementation strategies for the logic in ~6. 
2. The Syntax and Semantics of the Feature- 
Value Logic 
This logic is a quantifier free first order language 
with both set and sequence descriptions. Intuitively, 
the underlying set theory is zF- FA- SXT + A~A 
(where SXT is the axiom of extensionality, FA is the 
foundation axiom and AFA is Aczd's anti-foundation 
axiom). To cast this in more familiar terminology, 
two type identical elements of the domain need not 
be token identical. Token identity is indicated in the 
language via conjoining of the same variable to two 
or more descriptions. This is a generalisation of the 
notions of type identity and token identity familiar 
from conventional feature value logic semantics to 
set theory in general. Furthermore, we allow 
nonwellfounded structures. That is, nothing in the 
definition of the semantics prevents circular 
structures, i.e., structures which contain themselves. 
Otherwise, the set theory has the properties of 
classical set theory. However, in this paper, we will 
reconstruct the properties of the set theory we 
intend within standard set theory while observing 
that there is no difficulty in extending this treatment 
to either extensional or intensional nonwellfounded 
set theory. 
2.1. The Domain of Interpretation 
Every element, U i, of the universe or domain of 
interpretation, is a pair ~,~/) where i e N is the index 
and U is a structure which is one of the basic types. 
There are four basic types. They are constants, 
feature structures, sets and sequences. We will call 
a pair ~,u)an i-constant, i-feature structure, i-set or i- 
sequence according to the type of ¢/. The i- is an 
abbreviation for intensional. So, an i-set is an 
intensional set. Although we will carefully 
distinguish between i-types and basic types in this 
section, we may occasionally refer to basic types in 
what follows when we really mean i-types. 
We will use the following notational conventions. 
Script capitals denote the class of objects of basic 
types. +-superscripted script capitals denote the 
class of objects of the corresponding i-types. Bold 
script capitals denote elements of the types. Bold 
script capitals with superscript i denote elements of 
the i-types with index i. Capital Greek letters denote 
the class of descriptions of the i-types and lowercase 
Greek letters denote descriptions of dements of the 
i-types. I.e., ~ is the class of constants, ~r~ is the class 
of i-constants, ~ (e ~ is a constant, ~i (e .~+) = (i,~ is 
an i-constant, A is the class of i-constant descriptions 
and 0t (e A) is a description of an i-constant. We will 
also use +-superscripted bold script capitals to 
denote elements of an i-type when we don't need to 
mention the index. I.e., ~" e ~+ is an i-constant, etc. 
9-is the class of feature structures, ~(the class of sets 
and £ the class of sequences. ¢./= .~ u 9- u K u £ is 
the class of basic types. ¢/+ = ~" u ~+ k# ~+ u 5 + is 
the class of basic i-types, i.e., the domain of 
interpretation. Sets and sequences may be 
heterogenous and are not limited to members of 
one particular type. A feature structure 9 r e 9"is a 
partial function 9": ~ -# ~/+. We Will follow these 
conventions below in the presentation of the syntax 
and semantics of the language. 
2.2. Syntax 
2.2.1 Notational Conventions 
Below, we present an inductive definition of the 
syntax of the language. A is the set of i-constant 
descriptions, N is the set of (object language) 
variables, 4) is the set of i-feature structure 
descriptions, K is the set of i-set descriptions, Z is the 
set of i-sequence descriptions and 
= A u N u 4) u K u Z is the set of descriptions of i- 
structures (formulas) of the entire language. Object 
language variables are uppercase-initial atoms. 
(I.e., they follow the Prolog convention.) Lowercase 
Greek letters are metavariables over descriptions of 
structures of the corresponding intensional type. 
(E.g., ct eA is an i-constant description, ~ e 4) is an i- 
feature structure description, t: e K is an i-set 
description and q • Z is an i-sequence description. 
v e N may denote a structure of any i-type.) 
2.2.2. Definition 
Given the notational conventions, • is inductively 
defined as follows: 
(a) 
~) 
(c) 
(d) 
(e) 
(0 
aeA 
yeN 
~e K::=v 10 I{¥I ..... ~n} I~ClU ~21~1e Ic21\[o\] 
oe Z::=v 101OlOO21~ ..... ~n)lal u~ ~1 
(~I, .... Yn}<: I¥I ~ ¥21q® ~ 
Ve + ::--a Iv I# IVl ^+21Vl vW21-V 
- 104- 
2.2.3. Notes on the syntax 
We define V/1 "--~ V/2 to be -V/1 vv/2 and V/1 (-~V/2 to be 
(~V/I v V/2) A (~V/2 v v/l) in the usual way. 
Set descriptions ({V/l, .... v/n}) are multisets of 
formulas. Set descriptions describe i-sets of i- 
structures. A set union description 0¢1 u I¢ 2) 
describes the union of two i-sets. The union of two i- 
sets is an i-set whose second component is the union 
of the second components of the two operand i-sets. 
(Note that this definition means that the indices of 
the two subsets do not contribute to the union.) 
A sequence concatenation description (Ol *o2) 
describes the concatenation of two i-sequences. 
(Sometimes in grammars, we will be sloppy and 
write subformulas which denote arbitrary i-types. 
This should be understood as a shorthand for 
subformulas surrounded by sequence brackets). 
{V/1 ..... v/n}< describes an i-sequence of elements the 
order of which is unspecified. V/1 < V/2 describes an 
implicitly universally quantified ordering constraint 
over a sequence. The intuitive interpretation is: "V/1 
< V/2 is satisfied by a sequence if every element of 
the sequence that satisfies v/1 precedes (or is equal 
to) every element of the sequence that satisfies V/2". 
This is essentially the same interpretation as that 
given to GPSG LP constraints (as modified for 
sequences). 
2.2.4. Matrix notation and other abbreviatory 
conventions 
We will use a variant of the familiar matrix notation 
below adapted to the extra expressive power that 
our logic provides. We will briefly outline here the 
translation from the matrix notation to the logic. 
A conjunction of feature-value pairs 
al:v/l^ ... ^an:v/n is represented using the 
traditional matrix notation: 
I al:v/1 \] 
Lan:v/nl 
Any other type of conjunction is represented as 
specified above. The connectives --~, v, ~, ~--~are used 
in the normal way except that their arguments may 
be conjunctions written in matrix notation. For set 
(sequence) descriptions, "big" set (sequence) 
brackets are used where the elements of the set 
(sequence) may be in matrix notation. We will also 
often use boxed integers in the matrix notation to 
indicate identity instead of variables. The 
interpretation should be obvious. 
We will also use a few abbreviatory syntactic 
conventions. They should be obvious and will be 
introduced as needed. For example, the following 
formulas are formally equivalent 
V/1 < V/2 < V/3 
V/1 < v/2 ^ V/2~ V/3 
In addition, we will occasionally write partial 
ordering statements in which the first (second) 
description in the ordering statement is a variable 
which denotes a sequence. In this case, the intent is 
that the elements of the denoted sequence all follow 
(precede) the elements satisfying the other 
description. For example, if VP denotes a sequence 
of feature structures then the description 
cat: verb < VP 
stands for 
(cat:verb < Initial) ^ 
(NonVP u< (VP A ((Initial) • Tail))) 
and all of the dements of the VP sequence must 
follow any verb. Similarly, 
VP < cat: verb 
stands for 
(Final < cat: verb) ^ 
(NonVP u< (VP ^ (Front • (Final)))) 
and all of the elements of the VP sequence must 
precede any verb• 
2.3. Semantics 
An i-structure, ~i is an element of ¢/+• A function 
N -~ f2 + is an assignment to variables. A model is 
a pair (~i~ 
2.3.1. 
(a) 
2.3.2. 
Co) 
Constants 
~& ~ a i~,~ = ~,a) = ~,,~ (ie., a = a e ~0 
Variables 
(f.~',$) ~ v iff~(v) ffi ~ (v e N) 
2.3.3. Feature-value pairs 
(c) ~+~g) D a:v/iff F&z and ~y(a),~ ~ V/ 
2.3.4. 
(d) 
(e) 
(t) 
Classical connectives 
(7-/+,g) ~ V/I ^ V/2 iff (7./+,~ ~ V/1 and (¢./+,g) 
V/2 
(~+~g) ~ V/1 v V/2 iff (~/+4g) ~ V/1 or (~/+~ ~ V/2 
2.3.S. 
<g> 
(h) 
Set descriptions 
~+&~O 
(~t~4",$) ~ tc where z = {¥I ..... Vn} iff there 
exists a surjection z: n --~ ~s.t. 
Vie n: <~(i),g) ~ Vi 
- 105- 
(i) 
(~ 
(k) 
(9~'d) ~ Zl u z2iff3R+19~'2: K = g~ u ~and 
(~(+1,8) P Zl and (~+2,$) P K2 
(9C~,~) P Zl @ K2 iff Bg~+1R+2: K = ~ u ~and 
~,I c~ ~ = ® and (aC+I,~ ~ Zl and 
(K+,g), \[o\] fff BS+: ~+~), o and ~= \[3\] 
2.3.6. 
(D 
(m) 
(n) 
(o) 
(p) 
(q) 
(r) 
2.3.7. 
Sequence descriptions 
(()+~ ~ 0 
CJ+,g) ~ Ol • 02iff Id'lS+2:5 = $1 ,,92 and 
(J+l,g) ~ Ol and (3+2,~ \[= 02 
($+,~ ~ (tgl, .... Vn)iff3~'l ..... ~'n: 
5=(~r~ .... ~'n)and 
(qf'l,g) ~ Vl ..... (~/+n,g) ~ Vn 
(5+,g) D {VI ..... Vn}< iff 3R+: K= \[5\] and 
(~,e> ~ {w, .... Vn} 
Cd',g) ~ Vl < V2 iff 5 = (¢-P~I, .... ~'n)and 
Vij e n s.t. (~J+i,8) ~ VI and (¢t+j,Z~ ~ ¥2: i < j 
(~',g) ~ o I u_< o~2 iff 3S+'3+": ¢,.¢e,~ ~ Ol and 
~",g) ~ o2 and \[5\] = \[$\] u \[$'\] and n = 
length(S) and 1 = length(5) and m = 
length(,?) and 3~W' s.t. ~': 1 --->n and 
~": m -~n and range(~') ~ range(~") = n 
and Vi, j e ~': i < j ---> ~'(i) < ~'(j) and 
~i,j e ~': i <_ j --> ~'(i) $ ~'(j) 
(S+,g) ~ Ol @ o2 iff ~',g) ~ o 1 ~< 02 and 3~'~¢" 
as in (q) and range(~') c~ range(n") = 
Notes on the semantics 
Note that the set of syntactic constants A and the set 
of semantic constants A are the same, i.e., A ffi ~ and 
~'oc-n = c~. • is the sequence concatenation operator. 
It is a total function s: 5× 3 --->3. It is defined to be 
(~i ..... ~. (oi+i ..... ~n) = (~I, ..... Vn~ 
\[5\] is the underlying set of the sequence 5, i.e., the set 
consisting of the elements of sequence S. 
2.3.8. The feature structure notation for 
models 
Below we will use matrix notation for representing i- 
structures. Since i-structures are completely 
conjunctive, there is no indication of disjunction, 
negation or implication. Furthermore, the order of 
elements in i-sequences are totally specified so 
there are no partial ordering statements, l- 
structures are composed of only i-feature structures, 
i-sets, i-sequences and i-constants. 
Obviously, there are no variables in structures. 
Rather than explicitly indicate all indices of 
intensional structures, identity of two structures is 
indicated with boxed integers. 
2.4. A Partial Proof Theory 
We use a partial Hilbert-style proof theory 
consisting of one rule of inference and many axioms 
and axiom schema. Space prevents us from 
presenting even this partial proof theory. We will 
note briefly that many of the axioms allow rather 
large disjunctions to be inferred. For example, if we 
have a formula 
(1,2) ^ (SI • S2) 
then we can infer 
(($1 ^ 0,2)) • ($2 ^ 0)) v (($1 ^ (I)) • ($2 ^ (2))) v 
(($1 ^ O * (S2 ^ (1,2))). 
Similar axioms hold for most of the two place 
connectives in the language including sequence 
union. 
The only rule of inference is modus ponens. 
From a and a --# ~ infer \[~ 
3. The organisation of the grammar 
3.1. Basic organisation 
A = {81, .... 8m} is the set of lexical signs. P = {Pl, .... Pn} 
is the set of nonlexical signs. The s/gn axiom, ~Z e T,, 
encodes the signs A u P where 
~F.; (cat: Cat) -~ (81 v ... v 8m v Pl v ... v Pn). 
A model ~f satisfies a formula ¥ with respect to a 
theory ¢= {q ..... ~, written s¢~ a- ¥ iff 
~fP q ^...^ tnAV. 
(We assume that the individual formulas in a theory 
have disjoint variables. When they don't, the 
assumption is that the variables in the entire theory 
are renamed such that this property holds.) 
A sequence P is a category C iff 
rP h°n: P\]. 3~fs.t. S¢~r Lcat: C 
The set of all sequences Z of category C is 
Z = la rphon: II I 3~fs.t. ~¢~a-Lcat: C ajj. t 
(This provides the generates relation for a 
grammar.) 
3.2. Two Axioms 
The following two axiom schema are included in 
every grammar which we consider. 
The dtrs-phon axiom 
- 106- 
((phon: Phon) ^ dtrs:(phon: Xl ..... phon: Xn)) <-~ 
phon: (Xl • ... * Xn) 
This axiom states that the value of the phon feature 
is the concatenation of the phon features of the 
elements of the dtrs sequence in the same order as 
they occur in the dtrs sequence. This means that 
the phon sequence of any feature structure is 
completely fiat. That is, there are no embedded 
levels of sequence structure corresponding to 
phrase structure. 
The head-subcat-slash-dtrs axiom 
(head: Head) A (subcat: Subcat) ^ (dtrs: Dtrs) ^ 
(slash: Slash) ---> 
subcat: ({dtrs: X| ..... dtrs: Xn} (~ \[NonUnionSubcat\] 
Slash) A 
dtrs: ({Head} ® (Xl u~ ... u_< Xn) @ 
NonUnionSubcat) 
This axiom says that in any headed sign, any 
element of the subcat set is either an element of the 
slash set, an element of the dtrs sequence or is 
"unioned into" the dtrs sequence and that there are 
no other elements of the slash set or dtrs sequence. 
3.3. A simple example 
Consider the following three element lexicon. 
01 = 
-- phon: Phon 
cat: sentence rPhon: Omes)\] 
head: Lcat: verb J 
\[\[phon: Sub~Fphon: Obj'\] 1 
subcat:l|cat:np 11 cat:np it 
LLcase: nom_lLcase: acc .IJ 
dtrs: Dtrs 
-- slash: Slash 
rPhon: (he)l 
02=|cat: nP | 
Lcase: nom_\] 
Fphon: (her)l 
03 = |cat: np | 
Lcase: acc / 
Then the grammar Tis the one axiom theory '1"= {0} 
where 0 = cat: C -'->01 v02v03. 
That is, if a FS is defined for cat then it must satisfy 
one of 01, 02 or 03. Given this grammar, the only 
sentence defined is "he likes her" and the only NP's 
defined are "he" and "her". 
Consider the description 
phon: (X,likes,Y)\]. 
cat: C 
Then the minimal FS which satisfies it is 
- phon: (he, likes,her ) 
cat: sentence 
rPhon: @kes)lN 
head: Lcat: verb J 
fFP h°n: (he)l B rP h°n: <her)TB\] 
subcat:~/cat:np / '/cat:riP / ~'~ 
tLcase:nomj Lcase:acc j ; 
dtrs: {B, B, ~} 
- slash: {} 
4. An analysis of Dutch subordinate clauses 
In this section, we will present a toy analysis of 
simple Dutch subordinate clauses. The example 
that we will look at is the clause Jan Pier Marie zag 
helyen zzaemmen (minus the complementiser 
omdat). We require the following lexical entries. 
1an,:FPh°n: 0"n>l 
Lcat: np _\] 
•Piet,: Fph°n: (Piet> 1 
Lcat: np J 
rphon: (Marie)\] . 
'Marie': \[.cat: np J 
'zag": 
- phon: Phon 
cat: sentence 3 vfonn: 
fin | 
\['phon: (zag)'\]| 
head:/cat: verb | I 
Lvform: fin 3 l 
subcat: {01, 02, 03 } I 
dtrs: Dtrs l 
- slash: Slash ...I 
where 01, 02, and 03 are: 
\['phon: Subj'\] 
01 = |cat: np | 
Lcase: nora _1 
Fphon: Obj~ 
02 = |cat: np | 
Lcase: acc / 
~phon: VP 
03=\]cat:vp | 
Lvform: infJ 
- 107 - 
'helpen': 
i phon: Phon "\] 
cat: vp | 
vform: inf | 
Fph°n: @elpen)l \[ 
head:/cat: verb \] / 
Lvform: inf J. | 
ffph°n:NP7 rP h°n:vP7\] I 
subcat: ~/cat: np I,/cat: vp /~" I 
LLcase: acc_l Lvform:infU \[ 
dtrs: Dtrs l 
slash: Slash J 
'zwemmen': 
i phon: Phon cat: vp 
vform: inf 
rPhon: (zwemmen~\] 
I head:/cat: verb / I Lvform: 
inf J 
\[ subcat: {} 
\[ dtrs: Dtrs 
L slash: Slash 
We also need the following axioms. 
cat: (vp v sentence) ^ subcat: ({(cat: vp) ^ (dtrs: 
Dtrs) ^ VP} u X) ~ ((extra: - ^ dtrs: (Dtrs u_< Y)) v 
(-extra: Z ^ slash: (\[VP} u W))) 
dtrs: Dtrs ---~ dtrs: (cat: np _< cat: verb A 
case: nora _< case: acc) 
((head: Head) ^ (dtrs: Dtrs)) ---) 
dtrs: (Head _< cat: verb) 
The first axiom simply states that VP complements 
are either extracted (i.e., members of the slash set) 
or are sequence unioned into the dtrs sequence. 
The second axiom says that NPs precede verbs and 
that nominative NPs precede accusative NPs. The 
third axiom says that a head precedes any other 
daughters in the dtrs sequence. This encodes the 
generalisation for Dutch subordinate clauses that 
governing verbs precede governed verbs. 
We'll now present the analysis. (We will necessarily 
have to omit considerable detail due to 
considerations of space.) We start as indicated in §3 
with the following description 
phon: (\]an,Piet, Marie,zag,helpen,zwemmen)^ cat: C 
The sign axiom will have the disjunction of the six 
lexical entries in its consequent. Since our formula 
is specified for cat, thus satisfying the antecedent of 
the sign axiom, we can apply the sign axiom. The 
disjunct that we will pursue will be the one for 'zag'. 
This means we infer the formula 
- phoni (Jan,Piet, Marie,zag, helpen,zwemmen> = 
cat: sentence 
vform: fin 
FPhon: (zag)\] 
head: lcat: verb | 
Lvform: fin J 
subcat: {¢1, ¢2, ¢3 } 
dtrs: Dtrs 
- slash: Slash 
(where ¢I, $2, ¢3 are as in the lexical entry for 'zag'). 
From the head-subcat-slash-dtrs axiom we can 
infer a large disjunction one of whose disjuncts is 
- phon: (Jan,Piet, Marie,zag, helpen,zwemmen>q 
cat: sentence \] 
vform: fin / 
l rPhon: (zag)\] \[ 
head: /cat: verb / ^ D4 I 
Lvform: fin J / 
subcat: {D1 A ¢1', D2 ^ ¢2', ¢3' } J 
dtrs: (D1,D2,D3,D4,D5,D6) 
slash: {} 
where ¢1', ¢2' and ¢3' are: 
rphon: (Jan)'\[ ¢1'= \[cat: np \[ 
Lcase: nomj 
rPhon: (Pie)'\] ¢2'= \[cat: np \[ 
Lcase: acc j 
¢3'= I 
phon: (Marie, helpen, zwemmen) 7 
eat: vp / 
vform: inf \[ 
dtrs: (D3,D5,D6) j 
Again, we can apply the sign axiom to each of these 
embedded formulas. ¢I' and ¢2' will be consistent 
with the lexical entries for 'Jan' and 'Pier' 
respectively and can be rewritten no further. ¢3' will 
be consistent with the lexical entry for 'helpen' so we 
will be able to infer 
- 108 - 
I phon: (Marie,helpen, zwemmen) - cat: vp vform: inf rphon: (helpen)l head:/cat: verb / Lvform: inf J 
I fFPhon: N M rphon: \]) vp 
subcat: ~\[cat: np I,\[cat: vp /t 
(.Lcase: accJ Lvform: infJJ 
dtrs: (D3,D5,D6) 
L. slash: Slash 
Again, from the head-subcat-slash-dtrs axiom we 
can infer a large disjunction one of whose disjuncts 
is 
- phon: (Marie, helpen,zwemmen)-\] 
cat: vp / 
vform: inf I 
-phon: ~helpen)'\] I 
vform: inf J I | 
subcat: {04' ^ D3, 05' ^ D6 } / 
J dtrs: (D3,D5,D6) -- slash: {} 
where 04' and 05' are 
\['phon: (Marie)'\] 
04'=/cat: np I 
Lcase: acc j 
\['phon: (zwemmen>'\] 
$5'= Icat: vp l" 
Lvform: inf .J 
Again the sign axiom can be applied to the 
subcategorised accusative NP and VP. The NP is 
consistent with the sign for 'Marie' and no further 
rewriting is possible. The VP is consistent with the 
sign for 'zwemmen' and so we can infer 
F phon: (zwemmen) ,i cat: vp 
I 
vform: inf \[ 
hon" zwemmen / .< >1I 
I head: | cat: verb I I I 
Lvform: inf i I 
I subcat: 0 I 
I dtrs: I 
slash: Slash ..a 
Again, the head-subcat-slash-dtrs axiom can be 
applied leaving only one possibility in this case, 
namely, that both dtrs and slash has value O. No 
further rewriting is possible. Under the assumption 
that the proof theory axioms that we have used are 
sound, we have determined that the original clause 
is in fact a finite sentence of the theory. 
There are two other points to make about the 
analysis. First, the first axiom we gave above 
guaranteed that VP complements which are 
specified extra: - are sequence unioned into the 
surrounding sign while NPs are not. We simply 
chose the extra: - option for every complement VP. 
Second, although we freely guessed at the values of 
dtrs sequences (within the limits allowed by the 
head-subcat-slash-dtrs axiom) a quick glance will 
establish that every dtrs sequence obeys the 
ordering constraints expressed in the second and 
third axioms. 
A few words are in order about how we can 
accomodate "canonical" German and Swiss- 
German subordinate clause order. In either case, 
the first axiom is maintained as is. For German we 
need to either eliminate the strict ordering 
condition concerning case of NPs in the second 
axiom or add disjunctive ordering constraints for 
NPs as Uszkoreit suggests. The ordering constraints 
for Swiss-German are essentially the same. The first 
half of the consequent of the second axiom must be 
maintained for German. For Swiss-German, 
however, this constraint must be eliminated. It 
seems that the correct generalisation for at least the 
Zfirich dialect (Zfiritfifisch) is that NP complements 
need only precede the verb that they depend on but 
not all verbs. (Cf. Cooper 1988.) Therefore, for 
Zfiritfifisch we must add an axiom something like 
subcat: ({cat: np ^ NP} u X) ^ head: (cat: verb ^ Verb) 
dtrs: (NP < Verb). 
(This condition is actually more general than the 
first half of the consequent of the original second 
axiom. I.e., it is a logical consequent of the second 
axiom.) 
For German, the third axiom is simply the one for 
Dutch with the order of Head and cat: verb 
reversed. This encodes the generalisafion for 
German subordinate clauses that governed verbs 
precede governing verbs. For Zfiritiifisch, the third 
axiom is simply eliminated since verbs are 
unordered with respect to each other. 
This analysis has been oversimplified in every 
respect and has ignored a considerable amount of 
data which violates one or more of the axioms given. 
It is intended to be strictly illustrative. It should, 
however, indicate that for "canonical" subordinate 
clauses, the differences which account for the 
variation in Dutch, German and Zfiritfifisch word 
order are fairly small and related in straightforward 
ways. It is this aspect which we briefly address next. 
5. Parametric Variation 
- 109 - 
If T1 and T2 are theories and T1 ~ T2, then T2 is a 
subtheory of T 1. This means that T2 axiomatises a 
smaller class of algebraic structures than T1. 
Typically, T1 (and T2) contain many implicational 
axioms. The implicational axioms of T1 actually 
limit the class of structures which T2 axiomatises. A 
theory of universal grammar has a natural 
interpretation in terms of algebraic theories, 
subtheories and implicational axioms which 
potentially allows a richer account of parametric 
variation than the naive parameter setting 
interpretation. The approach is entirely analogous 
to the relation of the theories of Brouwerian and 
Boolean lattices to the general theory of lattices. 
6. Implementation 
There has been no work done yet on the 
implementation of the logic. There are at least 
three obvious implementation strategies. First, as 
implied in §3, parsing of a sequence P as a category 
C can be reduced to testing satisfiability of the 
formula phon: P ^ cat. C. This means that we 
should be able to use a general purpose proof 
environment (such as Edinburgh LF) to implement 
the logic and test various proof theories for it. 
Second, there is an interpretation in terms of head- 
driven parsing (Proudian and Pollard 1985). Third, 
we might try to take advantage of the simple 
structure of the grammars (i.e., the dependency of 
phon on dtrs sequences) and implement a parser 
augmented with sequence union. We hope to 
investigate these possibilities in the future. 
7. Conclusion 
There are several comments to make here. First, 
the specific logic presented here is not important in 
itself. There are undoubtedly much better ways of 
formalising the same ideas. In particular, the 
semantics of the logic is unduly complicated 
compared to the simple intuitions about linguistic 
structure whose expression it is designed to allow. 
Specifically, a logic which uses partially ordered 
intensional sets instead of sequences is simpler and 
intuitively more desirable. However, this approach 
also has its drawbacks. What is significant is the 
illustration that syntactic structure and a treatment 
of nonconfigurational word order can be treated 
within a single logical framework. 
Second, the semantics is complicated a great deal 
by the reconstruction of intensional structures 
within classical set theory. A typed language which 
simply distinguishes atomic tokens from types and 
the use of intensional nonweUfounded set theory 
would give a far cleaner semantics. 
axiomatisation is still in work. This is largely due to 
the complexity of the semantics of set and sequence 
descriptions and the belief that there should be an 
adequate logic with a simpler (algebraic) semantics 
and consequently a simpler proof theory. We 
simply note here that we believe that a Henkin style 
completeness proof can be given for the logic (or an 
equivalent one). 
8. Acknowledgements 
I would first like to thank Jerry Seligman. If this 
paper makes any sense technically, it is due to his 
great generosity and patience in discussing the logic 
with me. I would also like to thank Inge Bethke for 
detailed comments on the semantics of the logic 
and Jo Calder and Ewan Klein for continuing 
discussion. Any errors in this paper are solely the 
author's responsibility. 
9. References 
Aczel, P. (1988) Non-Well-Founded Sets. CSLI 
Lecture Notes No. 14. Stanford. 
Bresnan, J. (Ed.) (1982) The Mental Representation 
of Grammatical Relations. Cambridge, 
Mass.: MIT Press. 
Cooper, K. (1988) Word Order in Bare Infinitival 
Complement Constructions in Swiss 
German. Master's Thesis, Centre for 
Cognitive Science, University of Edinburgh, 
Edinburgh. 
Gazdar, G., E. Klein, G. K. Pullum and I.A. Sag. (1985) 
Generalised Phrase Structure Grammar. 
Cambridge: Blackwell, and Cambridge, 
Mass.: Harvard University Press. 
Kasper, R. and W. Rounds. (1986) A Logical 
Semantics for Feature Structures. In 
Proceedings of the 24th Annual Meeting of 
the Association for Computational 
Linguistics, Columbia University, New York, 
10-13 June, 1986, 235-242. 
Johnson, M. (1987) Attribute-Value Logic and the 
Theory of Grammar. Ph.D. Thesis, 
Department of Linguistics, Stanford 
University, Stanford. 
Pollard, C. and I. Sag. (1987) Information-Based 
Syntax and Semantics. CSLI Lecture Notes 
No. 13. Stanford. 
Proudian, D. and C. Pollard. (1985) Parsing Head- 
Driven Phrase Structure Grammar. In 
Proceedings of the 23rd Annual Meeting of 
the Association for Computational 
Linguistics, University of Chicago, Chicago, 
8-12 July, 1985,167-171. 
Smolka, G. (1988) A Feature Logic with Subsorts. 
Lilog-Report 33. May, 1988, IBM 
Deutschland, Stuttgart. 
Third, the programme outlined here is obviously 
unsatisfactory without a sound and complete proof 
theory. The entire point is to have a completely 
logical characterisation of grammar. A complete 
110 - 
