Vector Space Semantics: a Modeltheoretic Analysis of Locative Prepositions
Joost Zwarts *           Yoad Winter t
Abstract
This paper introduces a compositional semantics of locative prepositional phrases which is based on a vector space ontology. Modeltheoretic properties of prepositions like monotonicity and conservativity are defined in this system in a straightforward way. These notions are shown to describe central inferences with spatial expressions and to account for the grammaticality of preposition modification. Modeltheoretic constraints on the set of possible prepositions in natural language are specified, similar to the semantic universals of Generalized Quantifier Theory.
Key words: natural language, semantics, preposition, locative, vector, monotonicity, generalized quantifier
1     Introduction
The last two decades have seen remarkable development in compositional modeltheoretic semantics of natural language. The idea that natural language expressions can be directly interpreted in the model of discourse has gained significant support in various domains. It led to a better understanding of inference in linguistics with close relation to syntax, helped to characterize linguistically relevant classes of expressions, and revealed systematic constraints on their possible meanings. Quite independently of these developments, much work in the fields of cognitive and conceptual semantics has acquired a significant body of knowledge about the semantic behaviour of prepositional phrases (PPs). In the modeltheoretic framework, however, the semantics of PPs has remained, to a large extent, unexplored. Our aim in this paper is to contribute for bridging this gap.
We refine and extend the proposal in Zwarts (1997), who argues for a vector space as the underlying ontology in the compositional analysis of locative PP structures. In section 2 we introduce a general semantic framework that uses such a model. Section 3 studies some denotational properties of prepositions in the proposed system. Certain properties introduced in Zwarts (1997) will be placed here in a wider perspective of preposition monotonicity. Two notions of monotonicity are defined and shown to be linguistically relevant in restricting the set of possible preposition denotations, accounting for central inferences and affecting grammaticality of modified PPs. An additional constraint, similar to the conservativity restriction on determiners, is shown to hold of natural language locative prepositions. Section 4 discusses more problems of locative preposition semantics and section 5 sketches a possible extension of the system to treat also directional prepositions.
*SIL, P.O. Box 44456, Nairobi, Kenya. Email: zwarts@net2000ke.com
^ Computer Science, Technion, Haifa 32000, Israel. Email: winter@cs.technion.ac.il
1
Throughout this paper, we presuppose familiarity with basic Linear Algebra and simple notions from Topology.1 Some useful definitions are summarized in an appendix.2
2    Locative PPs: Lexical Meanings and Compositional Interpretation
Sentences with spatial uses of prepositions show inferential regularities that are comparable with the much studied inferences with quantified expressions. For instance, like the determiner every, the preposition inside is transitive, in the sense illustrated in (1). The preposition near is symmetric similar to the determiner some, as exemplified in (2).3
A is inside B                            every A is B
(1)    B is inside C                            every B is C
(2)
A is inside C                            every A is C
A is near B                               some A is B
B is near A                               some B is A
As far as determiners are concerned, this kind of observations about inferences is the empirical basis for the generalized quantifier semantics of the noun phrase. That prepositions show similar consistencies is a reason to develop also a modeltheoretic semantics of the prepositional phrase, with a similar research agenda to the one of generalized quantifier theory (see e.g. Keenan (1996)).
2.1     A preliminary typology of spatial prepositions
The preposition is the most useful syntactic category in natural languages for expressing statements about space and movement.4 Locative prepositions are used to locate an object relative to another one, the reference object. For instance, in the predicative construction in (3a/b) the house is the reference object and the tree is the located object. Directional prepositions are more "dynamic" than the locative ones: they are usually connected to a verb or a noun expressing movement or direction as in (4a). Unlike the locative ones, the directional prepositions often resist predicative constructions, as exemplified below by the unacceptability of (4b).5
(3)      a. The tree is outside the house.
1Lang (1977) and Kelley (1961) are two of the many introductory textbooks in these fields.
2In the revision of this paper our attention was drawn to O'Keefe (1996), who develops a vector-based semantics of English spatial prepositions similar to ours in some respects, but motivated by cognitive-neurological considerations. A comparison must await future work.
3Symmetry with near is incomplete. For instance, reasonably due to pragmatic factors, the bicycle is near the house is OK whereas the house is near the bicycle is a weird sentence. Similar asymmetries hold for some. Compare for instance some people are politicians with some politicians are people.
4 Of course, in English there are non-spatial prepositions like for and despite. Most spatial prepositions can also be used for expressing non-spatial statements (e.g. Mary arrived on Tuesday). Further, spatial prepositions can be applied to abstract domains, as in the authorities above us or the events behind us. It has been proposed that such usages are based on certain geometric structures underlying such abstract domains. See for instance Jackendoff (1983), Gärdenfors (1994) and O'Keefe (1996:306-312).
5This criterion is not clear-cut, as also directional prepositions can sometimes be used in such constructions (cf. John is across the street). On this phenomenon, see Cresswell (1978), Jackendoff (1983) and Helmantel (1998), among others.
2
b. The tree is behind the house.
(4)      a. John walked to the park, b. ?John is to the park.
In this paper we concentrate on the locative prepositions and PPs,6 which can be further classified into projective and non-projective. A non-pro j ective preposition like outside in (3a) requires only spatial knowledge on the location of the two objects. By contrast, the projective preposition behind requires some further information about directions from the reference object. For instance, to determine whether (3b) is true, the shape and location of the tree and the house are not sufficient. The back side of the house should also be determined. This can change with the position of the speaker or conventions of using the house and hence it is not only a function of its intrinsic spatial properties. These distinctions between prepositions are fairly standard (cf. Herskovits (1986)) and they are further exemplified in table l.7
Locative prepositions		Directional prepositions
Projective	Non-projective	
above/over, below/under in front of, behind beside	in/inside, outside on, at near between	to, from into, onto across, around through
Table 1: typology of prepositions
2.2     The modification problem
Many locative PPs can be modified by expressions that involve some measure of distance or direction. For example, in addition to the "bare" PP structures of (3), there are also modified structures as in (5). Some other cases of PP modification are exemplified in (6).
(5)      a. The tree is ten meters [outside the house], b. The tree is ten meters [behind the house].
(6)   deep under the castle, diagonally above the door, far outside the city, right in front of the car
The reason these structures are classified as PP modification is because the additional expression syntactically applies to a PP (or a P-bar) to produce another PP (P-bar). The PP structure we assume throughout this work is given in figure 1.
Wunderlich and Herweg (1991), and more recently Zwarts (1997), raise the problem of how to give a compositional semantics to such structures. An a priori natural way to treat prepositions is as relations between sets of points (regions). For instance, a region A
6See section 5 for a preliminary extension of our proposal for directional prepositions.
7This table is of course far from exhaustive. We do not mention here spatial prepositions like after, against, alongside, amid(st), among(st), beneath, betwixt, beyond, by, down, nearby, past, throughout, underneath, and upon. See Jackendoff and Landau (1991) for an extensive list and discussion.
3
pp
P'
Mod                   P'
ten meters      P                    NP
outside            the house
Figure 1: PP structure in X-bar Theory
is outside a region B iff the two regions are disjoint: A(~\B = $. Compositionally, outside may then be treated as a function mapping a region A to the set of regions disjoint to it: outside(A) = {X : XC\A = $}. This predicate over regions compositionally applies to B: B <E outside(A). Suppose now that in (3a) and in (5a) the house occupies a region A and the tree occupies a region B consisting of a single point p. The compositional analysis of (3a) is straightforward and tantamount to p ^ A. In order to analyze compositionally also (5a), the denotation of the modifier ten meters should apply to the denotation of outside(A). To get the correct semantics, this function has to measure the distance between p and A. This is problematic, however, as A is not directly specified in the set outside(A). Of course, we can try to approach the problem by reproducing A from this set, which here is a possible strategy since A is the complement of Uoutside(A). However, the same ad hoc procedure would not correctly hold of (5b). A general compositional treatment of PP modification is not forthcoming if locative prepositions are taken as relations between sets of points.
Zwarts (1997) observes that since modifiers like ten meters and diagonally are predicates over distance and direction (respectively), also the function that a locative preposition denotes should return entities with measurable distance and direction. Zwarts proposes that these entities are vectors: directed line segments between points in space. Assume that an expression like outside the house denotes a set of vectors: roughly, the ones pointing outwards from the boundary of the house.8 Cases of syntactic modification as in (5)-(6) are naturally analyzed as (intersective) semantic modification: a modifier within a PP denotes a set of vectors that is intersected with the P' denotation. For instance, the intersection of the denotation of the measure phrase ten meters with a set of vectors W is the subset of W containing only vectors that are ten meters long: {«ef: \v\ = 10m}. Thus, the expression ten meters outside the house denotes the set of vectors pointing outwards from the house that are also ten meters long. Along the same lines we can obtain a correct treatment of many cases of PP modification.9 A locative preposition then denotes a function that applies to the set of points where the reference object is located and returns a set of vectors. The next section substantiates this proposal.
8As will be explained below, such a set of vectors may be mapped during the compositional analysis of the whole PP to an ordinary predicate over e type entities. 9 See more on modification in section 4.
4
2.3    Vector space ontology
A natural way to implement the proposal in Zwarts (1997) is to assume that vectors are the primitive spatial entity in models of natural language.10 Space ontology consists of a vector space V over the real numbers R. The element 0 e ľ is the zero vector and the functions + : (V x V) —> V and • : (R x V) —> V are vector addition and scalar multiplication respectively. We assume a positive scalar product f : (V x V) —>■ R+, standardly defining a norm | | : V —>■ R+. It is further assumed that V is an Euclidean n-space R". Drawing on this ontology, we define the domain of points Dp and the domain of vectors Dv. Dp is simply identified with V. Intuitively, each vector in V uniquely determines its end-point and vice versa. The domain Dv is defined as the cartesian product V x V. Each "point" w in Dp (= a vector in V) functions as "the center" (= the zero vector) of a vector space Vw C Dv. This is done as in the following definition.
Definition 1 (the vector domain) Let (V, 0, +, •) be a vector space over R with f a positive scalar product and w E V.  We define:
Vw   =f  {{w,v):vEV}
0W   =f   (w,0)
de f
ForaUu,vEV:   (w,u)+w(w,v)   =   {w,u + v} For all s E R, v E V:   s -w {w, v)   =   {w, s ■ v)
Forallu,vEV:   fw({w,u), (w,v))   =   f (u,v)
It is easy to verify that for every w EV: (Vw, 0w, +w, -w) is a vector space over R with fw a positive scalar product, which determines a norm denoted by | \w. Trivially, the domain Dv is equal to the union of vector spaces UweyVw To avoid confusion, we sometimes refer to vectors in Dv as located vectors, to distinguish them from vectors ("points") in DP = V.   ^
Notational conventions: p, q e Dp for points; u, v, w e Dv for located vectors; if
de f                                                                                                                    de f
u = (w,v) G Dv then s-point(u) = w E V is the start-point of u, e-point(u) = w + v E V is its end-point. The vectors w and w + v can be viewed as "points" p and q in Dp. These conventions are illustrated in figure 2. We sloppily use the symbols +, •, / and | | for operators on members of Vw, without mentioning the subscript w as strictly required. The domains Dp and Dv are treated as typed domains of types p and v respectively.
2.4    The compositional process
Reconsider the modified structures in (5). Given the assumptions above, the "semantic structure" of a modified PP with a modifier MOD, a preposition P and a reference object region REF is as follows:
(7) MOD,tn(P(pt)W(REFpt))
10This is a convenience rather than a necessity. A notational variant is to assume a point ontology together with a metric and treat prepositions as functions from sets of points to sets of ordered pairs of points, so vectors are indirectly represented. In our strategy the metric function is the one that is implicitly supplied, by the given scalar product.
5
q
Figure 2: notation for vectors and points
In words: a locative preposition maps the set of points standing for the reference object to a set of vectors that is intersected with the denotation of the modifier. This process of intersective modification is the same as the one commonly assumed with other modification constructions like the blue car, where the set of cars is intersected with the set of blue objects. The assumed denotation of a measure phrase modifier MOD is straightforward. For instance:
ten_meters'   =   Av.|v| = 10m
The constant m (for meter) is a positive real number with the familiar fixed relation to other similar measure constants (e.g. for foot). In general, the denotation of any measure phrase is a measure set of located vectors, defined as follows.
Definition 2 (measure set) A set of located vectors M C V x V is called a measure set   iff for all vi, u>i, V2,w2 G V: if {vi,Wi) E M and \wi\ = \w2\ then (v2,W2) G M.
That is, whether a located vector belongs to a measure set depends only on the norm of its second coordinate. It is easy to verify that the denotation of ten meters defined above, as well as the similar denotations of less than ten meters, more than ten meters, etc. are measure sets.
The denotation of a locative preposition P in (7) maps the reference object REF to a set of vectors. Such preposition denotations will be defined in the next section. The region REF itself is determined by the denotation of the e-type reference object. This is done using a location function loce^, which assigns any physical entity in De its location in space, or eigenspace (Wunderlich (1991)). Since the whole PP basically denotes a set of vectors, we have to translate it into an "ordinary" et predicate that standardly applies to the subject of predication (the located object). An "anti-location" function loc~ returns the objects located at the region determined by the set of vectors. This function is defined using loc as follows:
de f
loc~   =   \Wvt.\xe.y-p e loc(x) 3v e W[e-point(v) = p]
In words: loc~ maps any set of vectors W to the set of entities whose eigenspace is contained in the set of W's end-points.
To exemplify the process, sentence (5a) ends up denoting the following proposition.
(8) loc~(ten_meters' fl (outside'(loc(the_house'))))(the_tree')   ■&■
Vp G /oc(the_tree') 3v <E outside'(/oc(theJiouse')) [p = e-point(v) A |v| = 10m]
6
Proposition (8) claims that every point in the tree is an end-point of a 10m long vector starting on the house and pointing outside.11
In general, the types assumed for the syntactic categories in figure 1 are as follows.
NP      pt             (by loc)
P         (pt)(vt)
P'        vt
Mod    vt
PP      et             (by loc~)
We assume that the location function is a type shifting principle that adjusts the e type of the NP to its spatial use within the PP, specifying the pt eigenspace. In a similar way, the anti-location function shifts a P' denotation of type vt into the et denotation of the PP, which has a predicational function in the sentence. To complete the picture, we have to give the definition of preposition denotations.
2.5    Denotations of locative prepositions
Preposition meanings in natural language do not fully exploit the possibilities that mathematical theories of space allow. One example is convexity.12 Although speakers may well be aware that some object is not physically convex, there is a tendency to ignore this fact in many natural uses of such objects, which are often conceptually " convexized". For instance, although the bowl in figure 3a occupies a non-convex region, disjoint from the space occupied by the ball, this situation can nevertheless be described by the sentence the ball is inside the bowl. The bowl is conceived of as if it were a convex object, roughly of the shape indicated by the dashed line, which does contain the ball. Similarly, it is quite strange to say that in figure 3b the black circle is outside the grey ring. Rather, inside is more appropriate here.
Treating such effects would lead us too far afield (see Herskovits (1986)). Instead, we tentatively assume that the loc function maps entities only to convex eigenspaces. For similar reasons we assume that eigenspaces of objects are closed and non-trivial (= nonempty and properly contained in Dp). Regions that have these three properties are referred to as Topologically Simple. We assume that the loc function returns only topologically simple regions. Potential counter-examples like figure 3 often lead to hard puzzles. We speculate that these should be handled by a general theory of functional cognition and not necessarily by linguistic semantics. Such a theory should provide specific details about the cognitive parameters in the determination of the loc function.
The semantic task we are facing is to define (pt) (vt) functions for locative prepositions that respect basic inferences in natural language given the syntactic, compositional and ontological assumptions above. Let us first define some general relations that will be helpful in the semantic treatment of many prepositions.
11 Arguably, this condition is too strong because even one vector satisfying it would suffice for (5a) to be true. We believe, however, that this is due to pragmatic effects in the determination of loc: speakers' spatial conception of an object is often significantly different than its physical shape. Reasonably, even large objects like trees and houses can be represented as volume-less points. In such cases universal quantification as in (8) is indeed equivalent to existential quantification, as loc(the_tree') is a singleton. Trying to generally change the definition of loc~ so that in (8) we get an existential quantifier instead of the universal one would be more problematic. For instance, (3a) would become true even if only a tip of one leaf of the tree is outside the house.
12For the exact definition of convex objects, as well as for the other topological notions used below, see the appendix.
7
Figure 3: non-convex objects
Definition 3 (boundary vectors) Let v e Dv be a vector and A C Dp a set of points. We call v a boundary vector of A, and denote boundary (v, A) iff s-point(v) is in b(A), the boundary of A.
For example, in figure 4 v2 and v4 are boundary vectors of A whereas vi and v3 are not. Zero vectors starting (and ending) at the boundary of A are of course boundary vectors of A13
A	.		^r y4
	\	^      V2	
			
Figure 4: v2 and v4 are boundary vectors of A
Definition 4 (internally/externally closest vectors) Let v e Dv be a boundary vector of a set of points A C Dp. We say that v is a closest vector to A and denote closest(v,A) iff for every vector w e Dv that is a boundary vector of A s.t. e-point{y) = e-point(w): |v| < |w|. In case e-point(v) e A we call v internally closest to A and denote int(v,A).  Otherwise, we call y externally closest to A and denote ext(v,A).
Definition 4 imposes a condition of minimality: it classifies boundary vectors of a set of points A that are the shortest boundary vectors of A with the same end-point. Such a minimality condition is required because of the semantics of PP modification. For example, a point p as in figure 5 can be said to be exactly three meters outside the box A
13Note that boundary vectors exist if and only if the boundary of A is not empty. Thus, we assume that even "vague objects" like fog or clouds have boundaries specified by the loc function. However, as might be the case with all objects, there is no need to assume that the loc function is physically real in any sense.
8
only if the shortest vector connecting it to the box, v, is three meters long. The existence of longer connections that are three meters long (like w in the figure) does not falsify the sentence. In a similar way, p cannot be said to be diagonally above the box although w is a vector diagonal to the box. Only shortest connections that are diagonal to the box may characterize their end point as diagonal to the box.
		P	
	Si\		
	\v/	V	
A			
			
Figure 5: v is externally closest to A, w is not
Externally and internally closest vectors play a crucial role in our definition of locative prepositions. It is important to observe the relation that exists under the topological simplicity assumption between these notions and the intuitive definition of external/internal points using set membership. The following topological property (see Wall (1972:18)) is useful.
Proposition I If A and B are disjoint closed subsets of Rn and A is compact, then dist(^4, B), the distance between A and B, which is defined by the infimum inf ({dist(a, b) : a E A, b E B}), is positive.
By this property, we can show the following correspondence.
Proposition 2 Let A C Dp be a non-trivial closed set in Dp (= TV1). Then for every point p E Dp the following conditions are equivalent: (a) There is a vector v E Dv that is externally (internally) closest to A s.t. e-point(y) = p.     (b) p ^ A (p E A)
Proof: (a) =>- (b) directly by the definition of externally/internally closest vectors. Let us show (b) =>• (a).
1.    Assume p <£ A. {p} is bounded and closed in Rn, hence compact. Thus by proposition 1, dist(p, ^4) > 0. Let C be a closed sphere around p of radius r = dist(p, ^4). We will show CnA^0.
Assume by negation C(~\A = 0. By definition o/dist(p, ^4): for every e > 0 there is q E A s.t. r < dist(p,q) < r + e. The line segment [p, q] intersects b(C), the boundary of C, at point p'. Thus, 0 < dist(p', q) < e. C is closed, hence b(C) C C, so p' E C. Conclusion: dist(C, ^4) = inf({dist(p', q) : p' E C, q E A}) = 0. But C is bounded and closed in Rn7 hence compact. By our assumption C D A = 0. Thus by proposition 1, dist(C, ^4) > 0. Contradiction.
We conclude that C C\ A=£$. It is easy to show C fl A C b(Ä). Thus, for any q E C D A, the vector v E Dv from q to p satisfies r = |v| = dist(p, q) = dist(p, A). Therefore, v is externally closest to A with e-point{y) = p.
2.   Assume p E A. (b) =^ (a) trivially holds in case p E b(Ä): the zero vector from p to p is internally closest to A. In case p is in the interior of A, i(A), repeat the above proof for p and Dp \ i(A) (a closed set) and note that b(Dp \ i(A)) = b(A).
9
Consider first the prepositions in/inside and outside. In our proposal they map a set of points to the set of its internally/externally closest vectors respectively. Thus, we simply define:
, ..    in, inside:      in'= inside'   =   AAAvin£(v, A) outside:          outside'   =   \A.\v.ext(v, A)
The compositional procedure and proposition 2 guarantee that these definitions coincide with the intuition that inside and outside correspond to set containment and disjointness, respectively.
Corollary 3 Let the eigenspace /oc(a) of an object a be a non-trivial closed set. Then the following holds:
1.  b is inside a is true   iff locih) C /oc(a)
2.  b is outside a is true   iff locih) n loc(a) = 0
This seemingly trivial result shows that the vector semantics of prepositions like outside, designed to deal with their allowing for PP modification, still preserves the basic set-theoretical intuition of the point semantics. The achievement of both goals is not trivial.
It should be noted that (9) does not distinguish between in and inside although there are some important differences in the distribution of these two prepositions (e.g. in the air vs. * inside the air). We also ignore the many intricate meaning aspects of in discussed in Herskovits (1986) and Vandeloise (1991). For example, why do we say in the field but not in the prairie! Why don't we usually use the expression in the bowl when a bowl is upside down? Henceforth we put these questions aside, focusing on the more general semantic issues.
The other prepositions we define all give rise to regions that are outside the eigenspace, so the relation ext(v, X) is a part of their definition and each preposition imposes an additional condition on the vector v. This can be a condition on the length of the vector, as in the definition of on and at and of near:
de f
on, at:       on' = at'   =   XA.Xv.ext{v, Ä) A |v| < r0
(10)    near:         near'   =   \A.\v.ext(v, A) A |v| < r\
where r0 and r\ two small positive numbers r0 ~ 0 and r0 << r\
We interpret on and at as requiring almost zero distance between the objects. In the case of near the vector's length is said to be smaller that a pragmatically determined number r\.u The differences between on and at (like on the desk vs. at the desk) and many other interesting meaning aspects are again ignored. We refer here to the literature mentioned earlier.
The prepositions between and amid require a plural complement defining two or more reference objects. We define between' as corresponding to a non-constituent expression between...and.... This is because a more adequate treatment of such prepositions would require an analysis of plurality (see section 4). The three-place predicate between' relates two regions A and B with a set of vectors using the region co(A U B), the convex hull of A and B.
14Again, we are only interested in the general idea here and ignore all sorts of questions concerning the determination of this n, its dependence on the size of the reference object, etcetera. See Crangle and Suppes (1989) for discussion.
10
(11)  between...and...:
def
between    =   \A.\B.\v.[ext{v, A) V ext{v, B)] A e-point(v) e co(A UB)\A\B
For regions A and B as in figure 6, between'(.4) (B) is the set of vectors that are externally closest to A or to B whose end-point is in the shaded region.
Figure 6: between A and B
So far, we have defined only non-pro j ective prepositions. As mentioned above, projective prepositions require knowledge about directions in space. We assume that this is pragmatically determined using three orthogonal unit vectors in V for up, right and front, which are called axes. For every start-point w e V of vectors in Vw C Dv, an axis a e V determines an axis (w,a) e Vw that we denote a(w).
Consider the definition of the projective preposition above. The region that this preposition generates when the reference object is a single point x is illustrated in figure 7.
Figure 7: above x
In this diagram, the above-region consists of those vectors that make an acute angle with the up(x) axis.15 The way to define the preposition denotation so it derives this region is to allow only vectors whose vertical component (on up) is larger than their projection on the orthogonal component -Lup (=the horizontal plane). This is defined using the following fact from linear algebra (see e.g. Lang (1977:134)).
Proposition 4 For every v,a e V where a ^ 0 there is a unique scalar c(a,v) G R and a unique vector v±a s.t. v = c(a, v) ■ a + v±a. The scalar c(a, v) is called v's component along a and the vectors va = c(a, v) ■ a and v±a are called v 's projection on a and on -La respectively.
15In this figure and henceforth the axis is represented only by its direction and not by the underlying unit vector.
11
For a vector v e Vw and an axis a e V, we denote c(a, v) = c(a(w),v), va = va(y) and
v_La = v±a(uO-
The denotation of above is defined as follows:
(12)  above:    above'   =   XA.Xv.ext(v, A) A c(up, v) > \v±up\
An illustration of this definition is given in figure 7, where v is in the afrowe-region of x given the axis up. The definition of below (and under) is symmetrically:
def
(13)  below, under,    below'   =   \A.\v.ext(v,A) A c(—up,v) > \v±.
up I
Other projective prepositions work in a similar way but with other axes:
(■\a\  *n front °f-       in_front'   =   \A.Xv.ext{\, A) A c(front, v) > |vj_/ro„ř behind:             behind'   =   AAAv.exi(v, A) A c(— front, v) > |vj__yyX)„i|
The last preposition denotation we define is for beside. Its typical region has the shape as in figure 8. The definition of beside' is in terms of the absolute value of the component c(right,v):
def
(15)  beside:    beside'   =   \A.\v.ext(v, A) A \c(right, v)| > |vj
.right |
The vertical symmetry of the regions generated by this definition is due to the fact that an equivalent definition is obtained when replacing right by —right.
Figure 8: beside x
2.6     Example: transitivity of between
The compositional mechanism and the definitions of prepositions given above allow a correct analysis of many simple inferences. Let us illustrate that using a central one - the transitive behaviour of between:
A is between B and C (16)    D is between A and B
D is between B and C
The following proposition specifies the conditions under which (16) holds in the proposed system. For convenience we refer to A instead of loc(A), etc.
12
Proposition 5 a. If A,B, C and D are singletons {a}, {b}, {c} and {d}, then the inference (16) generally holds, b. Otherwise, (16) holds with the additional assumption D is outside C.
Proof: a. By definition if A C co(B U C) \ B \ C then a e [6, c] \ {b} \ {c} = (b, c).
Similarly d G (a, b).  Thus d E (b, c), or D C co(B U C) \ B \ C.
b. Assume A C co(B UC)\B\C.  Thus A C co(B U C). By definition of co: A U B C
co(B U C) and therefore co(A U B) C co(B U C) (i).
Assume further D C co(A UB)\A\B (U). By (i) and (ii): D C co(B U C). D n B = 0
by (ii). D n C = 0 by the proviso D is outside C. Concluding: D C co(B UC)\B\C as
required.
Note that without the assumption that D is outside C, the inference (16) does not necessarily follow, both intuitively and in our system. Consider figure 9 below. Although point A may be taken (for instance, by a spectator located on the line /) to be between the rectangle C and the line B, and although D is between A and B, the conclusion D is between B and C is of course illegitimate.
		A      _■----_ • - "	B/
--		D»	
	c		
Figure 9: inference (16) does not hold
3    Denotational Properties of Locative Prepositions
The study of various denotational properties of expressions in natural language is a prominent issue in modeltheoretic semantics. This enterprise is linguistically important in at least two different aspects: it helps to reveal constraints on possible meanings ("semantic universals") and it enables us to classify semantic properties of expressions that affect grammaticality. In this section, we will show that the vector space semantics of locative PPs has some non-trivial implications in both respects.
3.1     Point monotonicity
Let us call functions mapping sets of points to sets of vectors by the name prepositional functions. Since we are interested in the "pointal" behaviour of such functions let us concentrate on the end-points of vectors in the range of the function. For every prepositional function P we denote the corresponding function Pe from sets of points to sets of points as follows:
pe  dg  AA.Ap.3v e P (A) [p = e-point(v)]
13
The following definition characterizes the monotonicity of a prepositional function with respect to the set of points argument.
Definition 5 (point monotonicity) Let P be a prepositional function and X C Dpt.
1.  P is upward point-monotone over X (PMON7)   iff VA,BeX[ACB^ Pe(A) C Pe(B)}.
2.  P is downward point-monotone over X (PMON4.)   iff VA,BeX[ACB^ Pe(B) C Pe(A)}.
We specify point-monotonicity of prepositions according to the behaviour of their denotation over the domain X of topologically simple regions. Intuitively, point-monotonicity corresponds to truth preservation under enlargement/diminution of the reference object. For instance, knowing that Paris is in France, we may conclude that both (17) and (18) hold.
(17)  The house is in Paris =>■ The house is in France
(18)  The house is outside France =>• The house is outside Paris
This intuitively suggests that in and outside are PMON^ and PMON4. prepositions respectively. Indeed, the functions inside' and outside' defined above verify this expectation over the domain of topologically simple regions. Correspondingly, entailments (17) and (18) are established in the proposed system. More generally, the inference schemes below characterize the point-monotonicity of a preposition P.
P e PMONt:
qq\    A is in/inside B C is P A C is P B
P e PMON4.:
A is in/inside B C is P B C is P A
Other prepositions besides inside and outside are not point-monotone. Consider the preposition above for example. In figure 10 the sentence the bird is above the house is true, assuming that the bird is b and the house is H. However, the same sentence is false when we consider a much smaller house h, horizontally far from the bird, or a much larger house H', extending to contain the position of the bird. Hence, above is neither downward nor upward point-monotone. For similar considerations also the other locative
		
	• b                  H'	
	H	
Figure 10: above is not point-monotone
prepositions are not point-monotone. We propose the following universal.
14
Universal 1 Only inside' and outside' are possible PMONj" and PM0N4- denotations, respectively, for simple locative prepositions in natural language.
Consider the expression far from in English. Modeling it as a locative preposition in the by now obvious way, we get a PMONJ- prepositional function different than the meaning of outside. Universal 1 claims that this function is not a possible denotation for single word locative prepositions in any natural language. Note that far from in English is neither simple nor evidently locative. Rather, it is a compound (not necessarily constituent), derived from the directional preposition from. Unlike far from, a preposition like near, which is not point-monotone, is realized as a single lexical morpheme in many languages. Another example for possible meanings of prepositions that are ruled out by universal 1 are the following functions, sensitive to the diameter of the reference object. Recall the diameter of a set A is the "maximal" distance between two points in A. Formally it is defined as the supremum of the set {dist(x, y) : x,y E A}.
outside'djam<10(^4)(v)   iff outside' (A) (v) and diam(A) < 10
inside'diam>10(A)(v)   iff inside'(A)(v) and diam(A) > 10
These functions are PMONJ- and PMON1; respectively, but different than outside' and inside'.
The prepositions outside and inside are special in another respect. By proposition 2, over topologically simple objects the functions outside6 and inside6 coincide with set complementation and identity respectively. That is, for every topologically simple A C Dp: outside6(A) = A and inside6(A) = A. For all other preposition meanings in natural language, Pe is not set-theoretically definable without further assumptions on Dp (e.g. the above vector space ontology). Moreover, we propose:
Universal 2 For every prepositional function P referred to by a locative preposition in natural language, for every topologically simple region A: Pe(Á) C A or Pe(A) = A.
In other words, for every preposition P one of the following must hold:
A is P B   =>  A is outside B
A is P B  -£4>  A is inside B
Both inside and outside are thus unique in the system of natural language prepositions, one being the exception, the other the rule: the meaning of inside is the only preposition meaning that does not entail outside. One consequence of this universal is the elimination of prepositions that entail inside but are not entailed by it. For instance, an imaginable preposition *nearin satisfies A is nearin B iff A is inside B and A is close to B's edge. However, this preposition does not satisfy universal 2 and is unexpected to occur in any natural language. Another result is the elimination of prepositions that entail neither inside nor outside. For instance, a preposition meaning equivalent to either near or else inside is ruled out. These predictions are correct as far as we know.
As noted above, most prepositions are not point-monotone. However, there is a weaker property that is common to all prepositions.
Definition 6 (point continuity) Let P be a prepositional function and X C Dpt. P is point continuous over X (PCON) iff VA, B, C e X [A C B C C -+ Pe{A) n Pe(C) C Pe{B)Y
15
Obviously, point monotonicity entails point continuity. We keep concentrating on the domain X of topologically simple regions. Intuitively, a point continuity test is one that can be called the "Babushka inference". Suppose that Babushka 1 is inside Babushka 2, which is inside Babushka 3. The following inference holds of the PCON preposition beside:
(20) The ball is beside Babushka 1 and beside Babushka 3 =>- The ball is beside Babushka 2
We claim that the same holds of all prepositions.
Universal 3 All prepositions in natural language are point continuous.
This universal is similar to the continuity universal of Thijsse (1983) on "simple" NPs (universal U6 of Barwise and Cooper (1981)). Thus, continuity holds of determiners and prepositions alike. Universal 3 rules out an imaginable preposition *aboven that satisfies A is *aboven B iff A is an even number of meters above B. The prepositional function denoting such a preposition would not be PCON. Another example for a non-PCON prepositional function is the following:
outside'e!;eii(-diom) (^4) (v) iff outside' (^4) (v) and diam(A) is an even natural number
3.2    Vector monotonicity
Prepositional functions can be viewed as relations between sets of points and vectors. In order to examine monotonicity properties also with respect to the vector argument, we propose the following order on Dv.
Definition 7 (vector order) For all v,w e Dv: v < w iff there is s > 1 in R s.t.
W = SV.
Intuitively, < is a relation of lengthening over non-zero vectors v, w that have the same start point. For such vectors v < w iff v and w point in the same direction and |v| < |w|. It is easy to establish that this is a partial order on Dv.16 This allows us to define monotonicity with respect to the vector argument as well.
Definition 8 (vector monotonicity) Let P be a prepositional function and X C Dpt.
1.  P is upward vector-monotone over X (VMON'f)   iff y A e X Vu, v e Dv [u < v ->■ (P (Ä) (u) -)• P(A)(v))].
2.  P is downward vector-monotone over X (VMON^)   iff VieJŕVu,vÉDt[u<v4 (P (A) (v) -)• P(A)(u))].
Also with respect to this property we restrict our attention to the domain X of topologically simple objects. Intuitively, vector monotonicity corresponds to truth preservation when the located object gets further from/closer to the reference object. For instance, the following consideration suggests that the preposition behindis both VMONj" and VMON.J,. In a situation where Mary is between the tree and the house, both inferences (21) and (22) hold.
16i.e. it satisfies for all u, v, w g Dv: u < u (reflexivity), if u < v and v < u then u = v (antisymmetry), if u < v and v < w then u < w (transitivity).
16
(21)   Mary is behind the house  =>■  The tree is behind the house
(22)  The tree is behind the house  =>-  Mary is behind the house
More generally, the following inference schemes indicate vector monotonicity of a preposition P.17
P e VMONt:                                P E VMON4.:
/qo\    A is between B and C                   A is between B and C
A is P C_____________                 B is P C_____________
B is P C                                        A is P C
An example for a non-VMONt preposition is near, if A is near B and gets further from it, at a certain point it will no longer be near B. Some other examples are given in table 2.
VMONt_________________not VMONt
in front of - behind               near, on, at
above, over - below, under    inside, in beside                                   between
outside
Table 2: upward vector-monotonicity
Some remarks on this vector monotonicity classification of prepositions are in place. The status of beside as VMONt is not completely clear. It may be that in English this preposition carries an element of proximity, which would make it non-VMONt like the preposition near. As for between, this preposition is special in taking a plural NP as a complement. Therefore, we should test its vector monotonicity using a variation on the inferences in (23), as illustrated in (24). These semantic relations show that between should be classifed as downward, but not upward, vector monotone. This can formally captured using a straightforward variation on definition 8.
(24)      a. The cat is between the house and the fence (the tree). The cat is between the fence and the tree. ^4- The house is between the fence and the tree.
b. The cat is between the house and the fence (the tree). The house is between the fence and the tree. =r- The cat is between the fence and the tree.
It is assumed that the prepositions in and inside are not VMONt- This assumption follows from definition 8 and the (reasonable) definition of the denotation inside' in our system. Unfortunately, this classification cannot be supported by the test in (23): when an object A is between B and C, it is normally the case that A is outside B and C, and B is outside C as well. Thus the use of inside in (23) becomes contradictory.18
17To be precise, when the objects are not points there are certain marginal cases where these inferences are not very relevant for testing monotonicity. For instance, in figure 9 the point A may be considered above the rectangle C and between C and line B. Nevertheless, B is not above C.
18A JLLI reviewer points out to us that this case, although normal, is not the rule. For instance, we may say that Babushka A is between Babushkas B and C even in cases where A is inside B and C is inside A. We do not know how to deal with such effects.
17
While table 2 gives examples for prepositions that are not VMONy, examples for prepositions that are not VMONt are harder to find. The expression far from, mentioned above, could be considered a possible candidate. However, for similar reasons to the aforementioned, we do not take this as a counter-example to the following universal from Zwarts (1997).
Universal 4 All simple locative prepositions in natural language are VMONt-
Also the artificial preposition *not-close-to-and-not-far-from, with the obvious semantics, is not VMON+. Unlike far from it is not VMONt either.
Vector monotonicity is relevant to the grammaticality of PP modification. Consider the contrast between (25) and (26) vis-a-vis table 2.19
(25)      a. two meters in front of/behind/above/below the car
b.  ?two meters beside the car
c.  two kilometers outside the village
(26)      a. *two meters near/on/at the house
b.  *two meters in/inside the house
c.  *two meters between the two houses
Observing this compatibility, Zwarts (1997) proposes that modification of a PP using a measure phrase modifier is legitimate if and only if the PP is headed by a VMONt preposition. Consider, however, the following sentence in contrast to (26b):
(27)  The nail is 10cm inside the wall.
Modification in (27) is allowed although inside is not VMONt-20 Nevertheless, there is a possible contrast between the eigenspaces that are likely to correspond to the reference objects in the the two cases. We speculate that a wall as in (27) can be conceived of as an "unbounded" object: from the point of view of a person on one of its sides, a wall might have been unbounded on the other side. This is unlikely to be the case with the eigenspace of the house in (26b). Thus, we propose that the relevant property is not vector monotonicity of the preposition, but rather monotonicity of the set of vectors being modified. Vector monotonicity of sets of vectors is naturally defined as follows.
(28)  Let If C y x ľ be a set of located vectors. We say that W is VMONt (VMONt) iff for all u, v e V x V: if u e W and u < v (v < u) then v e W.
Note that a preposition denotation is VMONt/VMORJ, iff it maps any set of points to a VMONt/VMONt set of vectors. We propose that modification of a PP is acceptable when this set is VMONt (=closed under lengthening of its memebers). This is the general case
19Part of this contrast is observed in Wunderlich and Herweg (1991:780). They suggest that measure phrases can only modify prepositions that have an extra "directional" or "dimensional" argument (roughly, the axis of projective prepositions). Notice however, that outside (and inside in some uses mentioned below) does not have an axis argument, but can still be modified by a measure phrase.
20A reviewer of this paper points out that in, unlike inside, cannot be modified by measure phrases, and suggests that this fact should follow from the complex status of in-side. This may perhaps be the source of some other important differences between the two prepositions, but as mentioned above, the study of these must be deferred to another occassion. Note however that the empirical picture is quite complicated because in can be modified by adjectives like deep (e.g. deep in the forest).
18
with VMONt prepositions as in (25). The modified set of vectors can also be VMONj" with inside, due to the unbounded denotation of the reference object as in (27). However, when the preposition maps the reference object to a set of vectors that is not VMON^, modification is ruled out as in (26).
Why does vector monotonicity affect the acceptability of measure phrase modification? Our answer to this question is similar to Barwise and Cooper's (1981:183) reasoning about the relations between semantic properties of determiners and grammaticality of there sentences. Like Barwise and Cooper, we assume that certain grammaticality phenomena are affected by the motivation to avoid semantic trivialities like tautology or contradiction. In the case of PP modification, the modified PP has to guarantee that any non-trivial measure phrase modifying it would not lead to an empty set. Since the modified PP denotes a set of vectors, this condition is formally stated as the following requirement on such sets.21
Definition 9 (modification condition) Let W C V x V be a set of located vectors. We say that W satisfies the modification condition iff for every non-empty measure set M C V x V, the intersection M n W is also non-empty.
This condition takes care that an expression is modified by a measure phrase only when its denotation can guarantee that every measure phrase denoting a non-empty set would not lead to an empty set in the intersection process. By definition 2 of measure sets, we can easily prove the following fact.
Proposition 6 A set of located vectors W C V x V satisfies the modification condition iff W is VMONt, VMON; and non-empty.
Since by universal 4, all prepositions are VMON4-, the main factor affecting the acceptability of modified PP is whether the preposition is VMON'f" or not. A preposition like outside, which guarantees that the P' it gives rise to (outside the house) is VMON^, allows measure phrase modification because it can guarantee that no trivial measure set could lead to the empty set. A preposition like near, which is not VMON^, always gives rise to non-VMON^ sets. For instance, independently of the shape of the house, the P' near the house does not denote a VMON"f set, and consequently many measure phrases can modify it into the empty set (e.g. *5000km near the house). With the preposition inside, the possibility of modification depends on whether the reference object itself is VMONj" or not (cf. the contrast between * 10cm inside the house and 10cm inside the wall).
3.3    Preposition conservativity
In the proposed system there is an important relation between the two arguments of locative prepositions. Consider the following property.
Definition 10 (preposition conservativity) A prepositional function P is called conservative (CONSp)   iff VAVv [P(A)(v) -)■ s-point(v) G A].
A preposition is called conservative iff its denotation is conservative in every model. In a way that is similar to determiner conservativity,22 when P is a conservative prepositional
21Winter (1999) proposes to extend this condition using the analysis in Faller (2000) to modification processes with dimensional adjectives (e.g. 1.5 meters tall/*short) and comparatives (e.g. 30cm taller/shorter than John).
22Recall a determiner D is conservative iff B £ D (A) Hßnis D{A) for all A and B.
19
function the argument A restricts the set of possible elements in P (A): only vectors whose start-point is in A can be in P (A). We propose the following universal.
Universal 5 All natural language locative prepositions are conservative.
This claim is related to the following inference.23
(29)  A is n meters PB  4  The distance between A and B is n meters
All the prepositions discussed above are conservative. Correspondingly, (29) holds of all these prepositions when modification is grammatical and non-projective, in the sense of section 4 below.24 Consider, however, an artificial non-conservative preposition *behose, whose denotation is defined as behind something close to in the following way:
behose'(A)(v)   iff 3Spí[behinď(JB)(v) A Vp e B3w G near'(.4) [p = e-point(w)]]
This is a non-conservative preposition, which is VMONť and VMON.J. like behind. Thus, modification by measure phrases should be syntactically possible. However, (29) does not hold of this preposition. An object A can be 3 meters behind something close to B without the distance between A and B being 3 meters. Universal 5 expects prepositions equivalent to *behose to exist in no natural language. Below we mention another such non-preposition *inose, similarly defined as equivalent to inside something close to.
Like conservativity in the determiner domain, also preposition conservativity imposes a reduction in the number of possible denotations for lexical prepositions. To get an impression of that, let us tentatively assume that Dp C V is finite and \DP\ = n, and that Dv = {(w, v) G V x V : w G Dp and w + v G Dp}. That is, Dv is the set of vectors over the points in Dp. Let us denote PREP = D^pt^vty
Proposition 7 \PREP\ = l2"1^      \CONSP\ = 22n~1-n* Proof: \DV\ = n2 by definition.
PREP  =  {2D"YDp   "«*  22Dp*D*
Thus, \PREP\ = 22"<
CONSp  "£m  2^A'^e2DpxD- : s-pointMeA}
Let A G 2Dp be of cardinality i.  Thus, the set {w G Dv : s-point(w) G ^4} (the vectors in
Dv with start point in A) is of cardinality i • n.  Therefore we get:
\{{A,vr) G 2Ö" x Dv : s-point(w) G A}\
n
=  ^2(   . ) • i • n        ((   . ) - the number of subsets of Dp of cardinality i) i=o    %                                l
n              7?'                                  n_1    n — 1
Let us compare this result to the reduction D-conservativity imposes on possible determiner denotations (van Benthem (1984)):
(30)  For \De\ = n, |D(et)((eí)í) | = \DET\ = 24" whereas \CONSD\ = 23"
23As explained below, (29) is sufficient, but not necessary, for conservativity to hold. 24As to be pointed out there, when P is a projective preposition the sentence A is n meters P B is ambiguous, where only one reading allows inference (29).
20
P-conservativity is a weaker constraint than D-conservativity. It reduces the second exponent while the latter reduces the second base. The difference is clear from the following table, calculating the number of (conservative) Ds and Ps for n = 2, 3,4:
n	\DET\	\CONSD\	\PREP\	\CONSP\
2	65,536	512	65,536	256
3	~ 1.84 x 1019	~ 1.34 x 108	~ 4.72 x 1021	~ 6.87 x 1010
4	~ 1.16 x 1077	~ 2.42 x 1024	~ 1.16 x 1077	~ 3.4 x 1038
Already in a domain with 4 elements, D-conservativity eliminates more denotations than P-conservativity, although in this case the total number of preposition and determiner denotations is the same.
Note, however, that CONSp is not the strongest restriction we can obtain when also spatial properties are considered. On its own, it is not sufficient to guarantee the sound inference (29). In fact, if P(A)(v) holds then s-point(y) is not just any point in A, but rather a member of ^4's boundary that is closest to e-point(v). Measuring the reduction in possible prepositions that this spatial property imposes is much harder than with the set-theoretical property CONSp, so we must leave this question aside for the time being.
Recapitulation Let us note that the universals 1-5 are provably independent of each other. This can be shown by verifying that each of the artificial prepositions outsidedianKio/insidediam>io, nearin, outsideeven^am), not-dose-to-and-not-far-from, and inose is ruled out only by the corresponding universal.
4    Further Problems of Locative PP Interpretation
This section briefly discusses some additional problems in the semantics of locative prepositions.
4.1    Projective and non-projective modification
So far we have considered modified PPs like far outside the city, or ten meters above the house that involve a measure phrase modifier and license inference (29). Let us call such cases of modification non-projective, as the composition of the modifier meaning with the P' meaning involves no reference to axes from the reference object. Modifiers like diagonally and straight, by contrast, require a projective preposition and are sensitive to the projective information it encodes. For instance, sentence (31a) entails (31b), but not vice versa. It is natural to propose that this is because the meaning of (31a) requires, in addition to (31b), that the bird is located on the up axis of the house. Thus, let us refer to straight and diagonally as projective modifiers.
(31)      a. The bird is straight above the house, b. The bird is above the house.
Also non-projective modifiers like ten meters can give rise to projective modification. For example, sentence (32) can be true in a situation as illustrated in figure 11, where the vertical projection of the vector connecting the bird to the house is ten meters long.
(32)  The bird is ten meters above the house.
21
Figure 11: projective modification by ten meters
Note that under this reading of sentence (32) it does not license inference (29): the distance between the bird and the house in figure 11 is not ten meters.
Two questions that pose themselves are how to compositionally account for projective modification and how to correctly characterize its distribution with various modifiers and prepositions. As in the case of non-pro j ective modification, we propose that the two questions are strongly related. Projective modification of a set of vectors W is allowed whenever W uniquely determines an axis according to the following definition.
Definition 11 (axis determination) A set of vectors W C Dv uniquely determines an axis a e V iff a is the only member of {±up,±front,±right} s.t. there exists v e W with v_|_a = 0. In this case a is denoted a(W).
Thus, W uniquely determines a if a is the only axis parallel to a vector in W. We propose that projective modification is possible iff the set of vectors denoted by the P' uniquely determines an axis. If it exists, this is the relevant axis for the modification process. For instance, in (31a) and in (32) projective modification is possible because the set of vectors denoting the P' above the house uniquely determines the up axis. By contrast, consider the sentences in (33) and (34). In (33) the region denoted by outside the house contains vectors parallel to all six axes, so no axis is uniquely determined. Consequently, (33a) is unacceptable and (33b) can only be understood non-projectively: as asserting that the distance between the tree and the house is ten meters. Similarly, in (34) the region denoted by beside the house contains vectors parallel to two axes (right and —right). As a result, projective modification is unacceptable in this             well.
(33)      a. ?The tree is diagonally outside the house, b. The tree is ten meters outside the house.
(34)   ?The tree is straight beside the house.
More generally, all non-pro j ective prepositions like outside give rise to regions that do not uniquely determine an axis, and consequently disallow projective modification. Among the projective prepositions, beside is the only one that does not uniquely determine an axis. Therefore, this is the only projective preposition that disallows projective modification. This generalization is the second factor that determines grammaticality of modified PPs in our proposal.
(35)  Modification Generalization 2: A structure [P NP] can be modified by a projective modifier and allows a projective reading for non-projective modifiers iff its denotation uniquely determines an axis.
22
This generalization is accounted for in a straightforward way by the semantics we propose for projective modification. Consider first the lexically projective modifiers:
,    .    straight:        straight'(ri)(ct)   d=   \W.Xv.W(y) A v±a{w) = 0
diagonally:    diagonally'^{vt)   =   \W.\v.W(v) A \va{w)\ = \v±a{w)\
These natural definitions make use of the axis a{W) uniquely determined by the P' denotation W. When W does not uniquely determine an axis a, as in (33a) and (34), the result of applying the modifier to W is undefined.
As for non-pro j ective modifiers like far or ten meters, the projective reading is obtained by mapping a measure set Mvt into a modifier function, of type (vt)(vt). This is obtained using the operator proj, defined below.
(37)  proj{Mvt)  ^ XW.Xw.W{w)/\M{ya{w))
For instance, proj (ten_meters') maps any set of vectors W that uniquely determines an axis a to the set of vectors in W whose projection on a is ten meters long. Thus, the P' ten meters above the house denotes in its projective reading the set of vectors v above the house s.t. ten_meters'(vtip), or \vup\ = 10m. This is what is required to get the projective reading of sentences like (32). When W does not uniquely determine an axis, as in sentence (33b), the projective reading is undefined.
4.2    Boolean operations
One of the important test cases for compositional semantics is its behaviour under boolean conjunction, disjunction and negation. We should distinguish three compositional levels where boolean operators may apply in the analysis of the PP.
The PP level Since the proposed type of PPs is the et type of predicates, boolean operators at the PP level are treated standardly. For instance, an expression as in (38) is traditionally analyzed using set complementation and intersection of et type predicates.
(38)  not [pp ten meters above the mountain] but [pp four meters below the cloud]
The P' level At this level matters are more complex. It is necessary to consider negation, disjunction and conjunction separately. Negation of P' structures is impossible for some reason (probably a syntactic one). Consider for instance the ungrammatical strings *ten meters not above the house or * diagonally neither behind the chair nor in front of the table. To consider the implications of our proposal for the analysis such structures would therefore be linguistically irrelevant. With P' disjunction as in (39a) below, our semantics derives the proposition in (40). This proposition, assuming that the eigenspace for the bird in (39) is a singleton consisting of the point p, accounts for the equivalence between (39a) and the sentential disjunction in (39b).25
(39)      a. The bird is ten meters [above the house or below the cloud].
b. The bird is ten meters above the house or the bird is ten meters below the cloud.
25Unfortunately, when loc(h') is not a singleton equivalence does not follow. However, as mentioned in footnote 11, this is unlikely to happen when measure of distances as in (39) is involved.
23
(40)   /oc   (ten_meters' n (above'(/oc(b/)) U below'(/oc(c'))))(the_birdé)
<^  BvG ten_meters' n (above'(loc(h')) U below'(/oc(c'))) [e-point(v) = p] <^  BvG ten_meters' n (above'(loc(h')))[e-point(v) = p] V 3v e ten_meters' n (below'(loc(c')))[e-point(\) = p]
Among the boolean operations at the P' level, conjunction seems at first sight the most problematic for our proposal. Consider for instance (41a), which is intuitively equivalent to (41b).
(41)      a. The bird is ten meters [above the house and below the cloud].
b. The bird is ten meters above the house and the bird is ten meters below the cloud.
In our proposal, compositional intersection of the denotations for above the house and below the cloud normally leads to an empty set. This is because the vectors in these two sets are different: their starting points are in disjoint objects. Obviously, (41a) is not contradictory as this analysis implies. We would like to suggest that the origin for this problem is a phenomenon that appears also at the N' level of nominals and is known as "wide scope" conjunction. Compare the sentences in (41) with the sentences in (42).
(42)      a. Every cat and dog slept.
b. Every cat slept and every dog slept.
Compositional intersection of the two N' predicates cat and dog in (42a) would normally lead to an empty set. However, the prominent reading of the sentence is non-contradictory and equivalent to the sentential conjunction in (42b). Without getting into the analysis of this phenomenon,26 note the syntactic similarity between the PP in (41a) and the NP in (42a). In both cases the conjunction is at the X' level, and in both cases compositional intersection of two sets leads to insufficient results. We propose that the same mechanism that is relevant for the "wide scope" N' coordination in (42a) is responsible for the "wide scope" reading of the P' coordination in (41a).
The P level    Consider the following sentence.
(43)  The treasure is neither under nor beside the house. (Rather, it is inside the house).
The initial problem that such sentences evoke concerns the appropriate structure that should be assumed for the PP. In X-bar theory, where prepositions (being heads) cannot be coordinated, such cases can be analyzed as an instance of Right Node Raising, as in sentences like John hugged and Bill kissed Mary (see Neijt (1979:1-7)). A deletion analysis would assume that (43) is in fact a PP coordination where the noun phrase the house is deleted from the first conjunct. A syntactic analysis along these lines allows a straightforward semantic analysis of such cases in our framework.
For the sake of semantic generality, however, one may want a theory of prepositions to treat any case of coordination within the PP as base generated. We are not sure that this is a sound motivation, as the syntactic question seems here preliminary to the semantic one. Moreover, any possible treatment of modified structures that does not involve application of the modifier to the whole P' as in our system would not provide a base generated account
26For two different proposals see Hendriks (1993:89-95) and Winter (1995).
24
of the P' coordinations discussed above. Thus, it is preferable to start the semantic analysis of PP coordinations from a better syntactic understanding of these constructions than what available at present. Despite these qualms, let us indicate how cases like (43) might be treated if we wished to model P coordination as base generated. Note first that that sentence (43) entails (44).
(44)  It is not the case that the treasure is under the house.
A compositional analysis of the negative coordination neither under nor beside using our vector based preposition denotations would not respect this entailment. The reason is that the prepositional function under' n beside' maps any set of points A to a set of vectors that includes vectors with end-points that are under A. This is because the denotation under' maps A to the set of vectors whose end-point is under A and which are also externally closest to A. Consequently, any vector with an end-point that is under A but which is not externally closest to A belongs to the set under'(A). Thus, this set includes vectors with end-points under the house and the conclusion (44) is not guaranteed.
In order to overcome this problem let us first observe that all locative prepositions can be modeled using points while lifting the preposition denotation to range over vectors only when applying to the reference object. We can retain a former analysis and assume that lexically, every preposition P denotes a function / from sets of points to set of points. For instance, the "pointal" denotation of outside is outside6, which as shown above is simply the complement function. Now we can define a systematic mapping that shifts such a (pt)(pt) function / into the corresponding prepositional function fv in terms of vectors. This mapping is defined as follows:
(45)   fv   =f  \Apt.\v.closest(v,A) A f(A)(e-point{v))
Provably, (Pe)v = P for each of the prepositional functions P defined above. Thus, we may assume that all the locative prepositions are lexically defined as "pointal" functions Pe, but can be optionally lifted to their "vectorial" prepositional function P using the v operator.
Now, let us note that the problem with preposition negation does not arise when the boolean operators apply to the pointal functions. For instance, the coordination in (43) can be analyzed using the pointal functions under6 and beside6 as in (46). Only after all boolean operators apply at the P level can its denotation be shifted using the operator v into a prepositional function in terms of vectors.
(46)   /oc-((under6 n beside6f(/oc(h')))(ť)
This analysis leads to welcome results. Without reviewing the technical details in the interpretation of this formula, note that the function underenbeside6 is a pointal function that maps any set of points A to the set of points that are neither in under6 (A) nor in beside6(A). The prepositional function derived from this function using the " operator maps any set A to the set of A's closest vectors whose end-point is in under6 n beside6 (A) Thus, there is no vector in this set whose end-point is under A. This makes (46) entail the proposition denoted by (44) (under our constant assumption the eigenspace of the treasure is not empty).
A remaining question is what prevents application of the " operator before all boolean operations have applied at the P level. If application of this operator is free, then one expects also the following function to be a reading for neither under nor beside.
25
(47)  (under6)*' n (beside6)*7
This would immediately lead back to the problems that the pointal analysis comes to avoid. We would like to tentatively propose that analyses like (47) should be eliminated in a grammar with type driven translation, as introduced in Klein and Sag (1985). In Klein and Sag's proposal, every syntactic category has a specified semantic type. This specification drives the translation procedure so that each category ends up denoting objects only of its specified type. Assume that the type specified for prepositions is {pi){pi). Given that the " operator may shift this type into {pt){vt), it cannot apply in the translation of the P category in preposition negation or coordination. However, since in our system the type specified for the P' category is vt, the v shifting of the preposition must apply when translating the P'. Consequently, preposition meanings like
(47)  are ruled out because prepositions must denote {pi) {pi) functions. On the other hand, because the grammar requires that P' is given the vt type, these pointal functions cannot apply directly to the eigenspace of the reference object but rather in the translation of the P' they must be shifted first into {pt){vt) functions to satisfy the requirement.
Let us emphasize again that the proposal above for applying boolean operators to prepositions, which is admittedly too complicated, is irrelevant under many syntactic analyses that do not assume that coordinations as in (43) are base generated.
4.3    Plural reference objects
Our treatment has ignored questions that are related to plurality in the interpretation of PPs. However, all prepositions can take plural arguments (see (48)) and prepositions like between, among or amid even require a plural reference object (cf. (49)).2r
(48)  The tree is beside/near the houses.
(49)      a. The tree is between/among/amid the houses, b. *The tree is between/among/amid the house.
Cases like (49a) are of course evidence against the provisional denotation we have given to the non-constituent between...and.... A more general denotation of between takes a set of sets of points as argument, with the natural generalization of (11):
(50)   between:
between'((pt)í)(ví)   d=   XX^t)t.Xv3A e X[ext{v,Ä)] A e-point{v) G co{UX) \ UX
In order to use this definition, we should define the eigenspace of a plural object as the set of its parts' eigenspaces. Assume that part-of is a relation over the domain of entities, determined by the plural ontology (e.g. as in Scha (1981) or Link (1983)), such that part-of{x){y) iff y is one of the atoms supporting x. The location function of pluralities is defined by:
(51)   locf{{pt)t)   =;  Xx.XA3y[part-of{x){y)Aloc{y) = A]
For instance, if the entity denoting the houses stands for the collection {h'l7 h'2, h'3} then its eigenspace is the set of eigenspaces: {/oc(h'1), loc{h'2), loc{h'3)}. The semantics of sentences like (49a) is obtained in a natural way.
27In English, between prefers doubleton pluralities, a fact that we henceforth ignore.
26
In order to deal with cases like (48), with singular-taking prepositions, we do not need to change the semantics of the preposition itself. Rather, it is sufficient to define what happens when it gets a plural eigenspace (=a set of sets of points). This can be done by mapping a prepositional function P{j,t){vt) 1° a function Ppl that maps any plural eigenspace to the set of vectors P assigns to its convex hull:
(52)  Ppl  ^  AX(pi)i.Av.P(co(UX))(v)
This allows sentences like (48) to get their correct semantics with the "pluralized" prepositional functions besidep and nearp1.28
As Herskovits (1986) and Faller (1997) point out, sentences like (53) have an interesting reading: one that does not require that the worm is inside any strawberry.
(53)  The worm is in the strawberries.
This is captured by the pluralized prepositional function inp : even if the worm is outside each strawberry it may still be inside the convex hull of the strawberries' eigenspaces. This treatment also accounts for the lack of entailment in (54).29
(54)  a. The worm is between the strawberries b. Ť^ The worm is outside the strawberries
If the worm is in the convex hull of the strawberries, then it is not outside the strawberries, at least not in the "pluralized" sense of outside. Note that between does not entail in either, as exemplified in (55).
(55)  a. The child is between the houses b. t^ ?The child is in the houses
The reason for that is plausibly the distributive/collective ambiguity of plurals. Under the collective reading of (55b), the entailment might follow with the pluralized reading of in. But (55b) also has a prominent distributive reading equivalent to the child is in each house, with the singular reading of in, which of course does not follow from (55a). It is not clear to us, however, why the inpl reading that is observed in (53) does not appear in (55b).
5    On Directional Prepositions
Although this paper is basically about locative prepositions, our proposal would not be complete without some indication of how the framework presented here can be extended to directional prepositions. Unlike locative prepositions, which describe a static position of the located object, directional prepositions like to, from, and across are basically used to describe a change in location with respect to the reference object. Some examples follow.30
28This treatment resembles the "geometric description function" called outline in Herskovits (1986).
29This lack of entailment may seem to stand in opposition to universal 2. This is not the case however, as universal 2 officially refers only to singular prepositional functions, of the type (pt)(vt).
30There is a host of literature about the many different ways in which directional prepositions can be used. See Bennett (1975), Cresswell (1978), Helmantel (1998), Jackendoff (1983), Lakoff (1987), Nam (1995), Wunderlich (1991,1993) and references therein.
27
(56)      a. The car drove to the garage.
b.  The letter was sent from the office.
c.  The soldiers walked across the meadow.
At first glance, it may seem that we can use vectors directly in the semantics of such directional constructions by representing the movement of an object with a vector connecting the starting point and the end point of the movement. The interpretation of (56a), for instance, would then involve a vector that starts at an arbitrary point and ends at the garage, as roughly stated in (57b). Like locative PPs (cf. (57a)), a directional PP would then denote a set of vectors, but the difference is in the way the theme of the sentence relates to these vectors.
(57)      a. The car is standing behind the garage.
'the car is located at the end point of a vector pointing backward from the garage'
b. The car drove to the garage.
'the car was first located at the beginning point and finally at the end point of a vector pointing to the garage'
However, there are some indications that this is not the right approach. First, there are prepositions that require movements that are not simply described by a linear entity like a vector. The case of around is notable:
(58)  The car drove around the garage.
A second objection is that using only one vector to describe movement would make us lose the unified account of the role of the reference object in PPs. We saw that in locative PPs the reference object is always the origin of the vectors in the P' denotation. For any locative preposition P, the vectors in P (A) have their starting point in the reference object A. This cannot be maintained if we use an analysis as in (57b), where the vectors have their end point at the reference object. The situation becomes even less systematic with prepositions like through, where neither the end point nor the starting point of the required vector is at the reference object.
In view of these considerations, we will restrict the use of vectors to represent locations relative to a reference object, without letting the vectors indicate the route of the movement itself. Rather, the denotation of directional prepositions involves a more complex object that we will label a path, following the literature.31 A path will be modeled as a function from the real interval [0,1] C R to vectors. Locative prepositions determine static positions and therefore they map the reference object to a set of vectors pointing at potential locations for the located object. Directional prepositions determine a change in position and therefore they map the reference object to a set of sequences of vectors (=paths). Each of these sequences determines a potential change in position of the located object. For convenience, we identify the [0,1] interval with a domain D i of type i. Consequently, paths are functions of type iv and directional prepositions are functions of type (pt)((iv)t).
For instance, a path followed by the car in (58) could be the kind of function G that is roughly given in figure 12 (for a few points of the domain [0,1]). The denotation of the P' for around the garage is a set of such paths.  A full definition of the meaning of
28
0(0.25) _	
	\ i
\         ^—	—-; ©(oj)
0(0) N^^^ \	/ /
0(1)    ^__	" " 0(0.75)
Figure 12: a typical path for around
around should specify the mapping from sets of points to their corresponding "surrounding paths".
We follow Jackendoff (1983) (among others) in treating a path as a function from a non-temporal interval into space. This is in view of atemporal usages of directional prepositions as in the following sentences.
(59)       a. The trees are standing along the river.
b.   This road leads to the city.
c.   John looked through the window.
In these examples the path is used not for movement, but for locating plural or elongated objects or expressing the direction of someone's line of sight. It is the verb that determines what entity is related to the path and how it relates to the path. In (56) and (58) the subject is located on subsequent positions of the path on subsequent moments of time. In (59a) the trees are located on different positions of the path; in (59b) there is some sort of order-preserving mapping from parts of the road to positions of the path; in (59c) John and the object he is looking at are located at opposite ends of the path. We think there are different ways in which the relation between the path and the verbal meaning can be implemented, but we will leave that implementation to future work since in the context of this paper we are more interested in the internal affairs of directional PPs.
The most important directional prepositions of English can be divided into three classes (see Jackendoff (1983)):
(60)       a. source prepositions: from, out of, off
b.   goal prepositions: to, into, onto
c.   route prepositions: through, across, along, around, over
The prepositions in (60a) specify where the path starts, that is they put a condition on 6(0). The prepositions in (60b) determine the last vector 6(1) of the path. The "route" prepositions of (60c) do not involve a particular vector in the path. Rather, they require that the path contains some vector(s) Q(x) with certain properties with respect to the reference object.
In order to define the meaning of directional prepositions, we note that many of them are related in systematic ways to locative prepositions, as shown by the following entailments.
31
See Jackendoff (1983), Crow (1989) and Nam (1995), among others.
29
(61)      a. John went out of the house =>- John was in the house
b.  Mary went into the room =>- Mary was in the room
c.  The train went through the tunnel =>- The train was in the tunnel
(62)  The bird flew over the field =>- The bird was aöowe the field
In (61) we see that the directional prepositions out of into and through are connected to the locative preposition in: the relevant paths must overlap an internal point of the reference object. In (61a-c) this condition applies to the initial vector, the final vector and an intermediary vector in the path, respectively. Also (62) shows a connection between the over path and an intermediary vector in it whose end point should be above the reference object. More correspondences like these are summarized in table 3 (see also Leech (1969) and Jackendoff (1983)).
Directional	Locative
from, to, via	at
off, onto, across	on
out of, into, through	in
over	above
along	beside?
Table 3: relations between directional and locative prepositions
These connections allow us to define the denotation of many directional prepositions using few systematic mappings on the meanings of locative prepositions. To do that, let us extend the notion of closest vector from section 2.5 to a notion of closest path, defined as follows.
Definition 12 (closest path) We say that a path O e Div is a closest path to a set of points A C Dp and denote closest(Q,A) iff for every x e IV Q(x) is a closest vector to A.
The mapping between a locative preposition and the corresponding directional prepositions is defined using an operator dir that for any locative prepositional function P and a subset of the interval Di yields a directional prepositional function. This is defined as follows.
(63)   dir{Ilt){P(pt){vt))   =f XApt.XQw.closest{Q, A) A 3x e I[P{A)(0(x))]
In words: dir(I)(P) maps any set of points A to the set of closest paths to A whose value on some member of I is in P (A).
For deriving source, goal, and route directional prepositions from locative prepositions we use the following abbreviations:
source:    dir0 = dir{{0})
(64)    goal:        dir1 = dir({l}) route:      dir3 = dir([0,1])
These operators derive directional prepositional functions as follows:
30
from' = dir0 (ať)   off' = dir0 (on')         out_of = dir0 (in1)
(65)    to' = dir1 (ať)        onto' = dir1 (on')       into' = dir1 (in') via' = dir3 (ať)       across' = dir3 (on')   through' = dir3 (in')
(66)    over' = dir3 (above')   along' = dir3 (beside')
For instance, out_of' is the function that maps any set of points A to the paths 6 satisfying in'(^4, O(0)). Substantiating the compositional semantics of verb phrases, this treatment should directly account for entailments as in (61)-(62). Note that since our semantics of on and at is the same, also from and off, to and onto, and via and across get the same meaning. The intricate differences between these prepositions are not accounted for.
The directional prepositions defined in (65)-(66) are lexical items in English. We would like to propose, following Jackendoff (1983) a.o., that the dir mapping applies also compositionally to locative prepositions. For instance, a locative preposition like under (cf. (67a)) can be "directionalized" as in (67b).
(67)      a. The duck is under the bridge.
b. The duck swam under the bridge.
The directional effect in (67b) can be achieved using the dir3 operator.32 The locative preposition under has no corresponding directional preposition. By contrast, over is a lexically directionalized above. Which directional prepositions are lexically manifested and which ones are not is subject to vast cross-linguistic variation. For instance, both Hebrew locative prepositions mitaxat ("under") and me@al ("above") have no corresponding directional prepositions. Of course, this does not hurt the expressibility of directional statements in Hebrew: Hebrew me@al can be used in directional constructions just like English under in (67b).
Note that only the locative prepositions at, on, and in have a full pattern of source and goal prepositions. This suggests that these prepositions have a special, more basic status. We propose the following universal.
Universal 6 If PilT is a directional preposition whose meaning is either dir (Ploc) or dirl{Ploc),for some locative prepositional function Ploc, then Ploc is at'? on' or in'.
This universal rules out, for instance, a hypothetical directional preposition *from-Over, whose meaning would involve paths starting at points above the reference object.
The "directionalized" locative prepositions in (65)-(66) do not exhaust the inventory of directional prepositions. Some directional prepositions, like towards, away from and around, are not definable in terms of the dir operator on locative prepositions. The reason is that these prepositions do more than just put a restriction on a single vector in the path: they require certain relations among vectors in the path. Maybe the simplest to define are the relations imposed by towards and away from. These prepositions require that the end-point of the final vector in the path is closer to/further from the reference object than the end-point of the initial vector. Formally:
towards'   =
XA.XQ.closest(G,A) A dist(e-point(Q(l)), A) < dist(e-point(Q(0)),A)
awayjrom    =
XA.XQ.closest(G,A) A dist(e-point(Q(l)), A) > dist(e-point(Q(0)),A)
32Perhaps examples like he came from under the carpet and he went under the umbrella can be treated using application of dir0 and dir1 respectively.
31
This definition can account for entailments such as:
(69)      a. John is walking towards the house =>■ John is now closer to the house than he
was before
b. John is walking away from the house =>- John is now further from the house than he was before
The relation between towards and away from can be further exemplified by the following entailments:
(70)      a. The train moved back towards the station =>- The train had moved away from
the station
b. The train moved back away from the station => The train had moved towards the station
This kind of relation is more general and it appears also between pairs of source and goal prepositions from (60):
(71)      a. John moved back to Paris =>• John had moved from Paris
b.  Mary moved back out of the room =>- Mary had moved into the room
c.  The car moved back onto the field =>- The car had moved off the field
In each of these entailments the two prepositions can be replaced, preserving the entailment. The adverb back used in combination with a source/goal preposition implies an earlier movement in the opposite direction, which can be expressed by the corresponding goal/source preposition. These entailments can be explained as soon as we notice that these pairs of prepositions are each other's inverses in terms of path reversal. This is defined as follows:
(72) ~eiv =f \Xi.e(i-x)
~P(ptWv)t)   =   XA.XS3Q e P(A)[Q = ~6]
Note that from' = ~to', into' = ~out_of', off' = "onto', away_from' = "towards', and
conversely. This means that the semantics of back P can be formalized as Pn~P (ignoring the temporal aspect of back): a path in back P (A) is a path which is both in P (A) and in (~P)(^4).33 Notice that the route prepositions in (65)-(66) are their own reverse. For instance, through' = "through'. Correspondingly, entailments like the following hold for all route prepositions:
(73) The car moved back through the forest =>■ The car had moved through the forest
There are many interesting questions about directional prepositions which have not been discussed here. A full characterization of their denotational properties (e.g. mono-tonicity and conservativity) is yet to be given. We have also not discussed the composition of directional and locative PPs with verb phrases. This is important in order to formally account for inferences with verb phrase modification, which is one of the central ways to use prepositional phrases. We believe, however, that the ideas introduced in this section can form a basis for a more comprehensive study of directional prepositions in vector space semantics.
33If one considers the entailments in (71) to be presupposition relations rather than truth-conditional effects, it would be possible of course to replace this definition by a suitable presupposition, which would as well involve the reverse preposition of P.
32
6    Conclusions
Our investigation of the semantics of prepositions has drawn on some general principles that may be of importance for a more comprehensive semantic theory of spatial expressions. The ontological primitives in the proposed system are taken to be standard structures from mathematical theories of space. This step has the advantage of uniformity: all spatial expressions of a certain linguistic category (e.g. locative prepositions) are treated as having the same type of functions over the underlying space ontology. Unlike previous modeltheoretic approaches, notably Nam (1995), notions like spatial inclusion, betweenness or relative distance are not hard-coded in the ontology. These notions play an important role in our treatment as well, mainly in the monotonicity properties of prepositions. Inclusion is the boolean order on the power-set of the point domain; betweenness arises naturally from the ordering of the vector domain. However, no special axiomatic status is given to prepositions like inside or between. Their importance lies only in their appearance in central monotonicity inferences. We believe this is a welcome aspect of the proposed system, since it is hard to see what linguistic centrality these prepositions bear, when compared for instance with prepositions like outside or beside. A similar step of "modeltheoretic equality" had taken place before in the semantic theory of noun phrases, which gradually shifted from traditional logical views that emphasize existential and universal quantification, into the present uniform treatment of all NPs as generalized quantifiers.
The compositional process we have proposed is based on the motivation to let prepositions be the main locus for spatial reasoning. Prepositions denote purely spatial functions. The compositional interpretation of the PP ultimately treats the preposition as a relation between e type entities: the reference object and the located object. This is obtained indirectly, however, with the location function as the mediating "semantic glue" between non-spatial entities and the spatial preposition.
This shift between spatial and non-spatial domains may also be a point of relation between the semantic component and a cognitive component, responsible for the spatial conceptualization of physical objects. This process, although crucial for many objectives, has not been discussed at all in this paper. One reason for that (except for the authors' incompetence) is that under the topological simplicity assumption, the computation of many entailments can go on without putting any other restrictions on the loc function. Thus, full specification of the cognitive factors that affect it was not required, and one may even refuse to admit that this function has any "psychological reality" whatsoever. The theory can easily be tested against much solid linguistic data without addressing this question. This neutral, not to say agnostic, attitude towards psychological aspects of language use is shared by many contemporary studies in modeltheoretical semantics, but it was adopted here more as a practical route than as a matter of principle. We do believe that the rich linguistic mechanisms that are used for conveying spatial information can form an empirical basis for fruitful collaboration between logical semanticists and cognitive psychologists interested in natural language. We hope the present work might prove useful for such an exciting project.
A    Appendix: some useful definitions
A vector space over the field of real numbers R is a quadruple (V, 0, +, •) s.t. V is a set, 0 G V (the zero vector) and the functions + : (V x V") —>■ V (vector addition) and
33
• : (R x V) —> V (scalar multiplication) satisfy for all u, v, w G V and s, r G R:
1.   (u + v) + w = u + (v + w)
2.  Q+v=v+0=v
3.  There is an element —v G V s.t. v + (—v) = 0
4.  u + v = v + u
5.  s (u + v) = su + sv
6.   (s + r)v = sv + rv
7.   (sr)v = s (r v)
8.   lv = v   (1 is the unit element of R)
A scalar product over a vector space V is a function / : (V x V) —>■ R that satisfies for all m, v, iu G V" , s G R:
1.  f(v,w) = f(w,v)
2.  f (u, v + w) = f (u, v) + f (u, w)
3.  f(sv, w) = s f (v, w) = f (v, sw)
A scalar product is called positive iff for every v &V: f(v, v) > 0 and for every v G V\{0}: f (v, v) > 0. For a positive scalar product / the norm of a vector v G F is denoted M = "Jf{viv)-   We say that two vectors i7,iu G V are orthogonal (perpendicular) and
denote vl.w iff f(v,w) = 0. For any vector w G V we call _Lii7 = {d 6 ľ: i;J_ix;} the orthogonal complement of w.
For w, w; in a space l7, the line segment [v, w] is the set {sv + (1 — s)w : 0 < s < 1}. A set A C V is convex iff for all 17, w; G A: [v, w] C A The convex hull of A/ denoted co(A), is the smallest convex subset of V containing A
For any set X a metric for A" is a non-negative function d : (A x X) —>■ R+ that satisfies for all x, y, z G A:
1.  d(x,y) = d(y,x)
2.  d(:r, y) + d(y, z) > d(x, z)
3.  d(x,y) = 0 iff x = y
Note that the function dist(t>, w) = \v — w\ is a metric for y. A neighborhood in X of a point x G X is defined by Ux{x,5) = {y G X : d(x,y) < ö}. A set A C X is open in X iff for every x e A there is í > 0 s.t. Ux(x, 6) C A A C X is c/o5erf in X iff X \ A is open in X. The interior of i C X is the union of all open subsets in X contained in A The boundary of A is the set of points in X interior neither to A nor to X \ A The diameter of A is the supremum of the set {(x,y) : x £ A and y G A}. A set ^4 is bounded iff its diameter is finite. We do not define compact sets, rather only mention the Heine-Borel-Lesbegue theorem (see Kelley (1961:144)): a subset of an Euclidean n-space
34
Rn is compact iff it is closed and bounded.
Acknowledgements
This paper extends a shorter version that appeared in proceedings of Semantics and Linguistic Theory 1997. It was written when the authors were affiliated to the Utrecht Institute of Linguistics at the Utrecht University. The part of the first author was supported by the Foundation for Language, Speech and Logic, which is funded by the Netherlands Organization for Scientific Research, NWO (grant 300-171-033). We are grateful to Johan van Benthem and Ed Keenan for their remarks on this work.
References
Barwise, J. and Cooper, R. (1981). Generalized quantifiers and natural language. Linguistics and Philosophy, 4:159-219.
Bennett, D. C. (1975). Spatial and Temporal Uses of English Prepositions: an essay in stratificational semantics. Longman, London.
Crangle, C. and Suppes, P. (1989). Geometrical semantics for spatial prepositions. Midwest Studies in Philosophy, 14:399-422.
Cresswell, M. (1978). Prepositions and points of view. Linguistics and Philosophy, 2:1-41.
Crow, J. S. M. (1989). Towards a Semantics for English Spatial Expressions. PhD thesis, University of Texas at Austin.
Faller, M. (1997). Geometric description functions in a vector space semantics for locative PPs. Unpublished ms., Stanford University.
Faller, M. (2000). Dimensional adjectives and measure phrases in vector space semantics. In Faller, M., Kaufmann, S., and Pauly, M., editors, Formalizing the Dynamics of Information. CSLI Publications, Stanford.
Gärdenfors, P. (1994). Frameworks for properties: possible worlds vs. conceptual spaces. Sémiotiques, 6:99-120.
Helmantel, M. (1998). Simplex adpositions and vector theory. The Linguistic Review, 15:361-388.
Hendriks, H. (1993). Studied Flexibility: categories and types in syntax and semantics. PhD thesis, University of Amsterdam.
Herskovits, A. (1986). Language and Spatial Cognition: an interdisciplinary study of the prepositions in English. Cambridge University Press, Cambridge.
Jackendoff, R. (1983). Semantics and Cognition. MIT Press, Cambridge, Massachusetts.
Jackendoff, R. and Landau, B. (1991). Spatial language and spatial cognition. In Napoli, D. J. and Kegl, J. A., editors, Bridges between Psychology and Linguistics. Lawrence Erlbaum Associates, Hillsdale, NJ.
Keenan, E. (1996). The semantics of determiners. In Lappin, S., editor, The Handbook of Contemporary Semantic Theory. Blackwell.
Kelley, J. L. (1961). General Topology. Van Nostrand, Princeton, New Jersey.
Klein, E. and Sag, I. (1985). Type driven translation. Linguistics and Philosophy, 8:163-201.
Lakoff, G. (1987). Women, Fire, and Dangerous Things: what categories reveal about the mind. Chicago University Press, Chicago.
Lang, S. (1977). Linear Algebra. Addison-Wesley, Reading, Massachusetts, second edition.
Leech, G. N. (1969). Towards a Semantic Description of English. Longman, London.
35
Link, G. (1983). The logical analysis of plurals and mass terms: a lattice theoretical approach. In Bauerle, R., Schwarze, C, and von Stechow, A., editors, Meaning, Use and Interpretation of Language. De Gruyter, Berlin.
Nam, S. (1995). The Semantics of Locative Prepositional Phrases in English. PhD thesis, University of California Los Angeles.
Neijt, A. H. (1979). Gapping: a contribution to sentence grammar. PhD thesis, Utrecht University.
O'Keefe, J. (1996). The spatial prepositions in English, vector grammar, and the cognitive map theory. In Bloom, P., Peterson, M. A., Nadel, L., and Garrett, M. F., editors, Language and Space. MIT Press, Cambridge, Massachusetts.
Scha, R. (1981). Distributive, collective and cumulative quantification. In Groenendijk, J., Stokhof, M., and Janssen, T. M. V., editors, Formal Methods in the Study of Language. Mathematisch Centrum, Amsterdam.
Thijsse, E. (1983). On some proposed universals of natural language. In ter Meulen, A., editor, Studies in Modeltheoretic Semantics. Foris, Dordrecht.
van Benthem, J. (1984). Questions about quantifiers. Journal of Symbolic Logic, 49:443-466.
Vandeloise, C. (1991). Spatial Prepositions. Chicago University Press, Chicago.
Wall, C. T. C. (1972). A Geometric Introduction to Topology. Addison-Wesley, Reading, Massachusetts.
Winter, Y. (1995). Syncategorematic conjunction and structured meanings. In Proceedings of Semantics and Linguistic Theory, SALT5.
Winter, Y. (1999). Modification of prepositions and degree adjectives in vector space semantics: extending the analogy. Unpublished ms., Utrecht University.
Wunderlich, D. (1991). How do prepositional phrases fit into compositional syntax and semantics. Linguistics, 29:591-621.
Wunderlich, D. (1993). On German urn: semantic and conceptual aspects. Linguistics, 31:111-133.
Wunderlich, D. and Herweg, M. (1991). Lokale und direktionale. In von Stechow, A. and Wunderlich, D., editors, Semantik: ein internationales Handbuch der zeitgenösischen Forschung. De Gruyter, Berlin.
Zwarts, J. (1997). Vectors as relative positions: a compositional semantics of modified PPs. Journal of Semantics, 14:57-86.
36
Contents
1    Introduction                                                                                                                                     1
2    Locative PPs: Lexical Meanings and Compositional Interpretation                                    2
2.1    A preliminary typology of spatial prepositions.........................       2
2.2    The modification problem....................................       3
2.3    Vector space ontology......................................       5
2.4    The compositional process....................................       5
2.5    Denotations of locative prepositions    ..............................       7
2.6    Example: transitivity of between................................     12
3    Denotational Properties of Locative Prepositions                                                                  13
3.1    Point monotonicity........................................     13
3.2    Vector monotonicity.......................................     16
3.3    Preposition conservativity....................................     19
4    Further Problems of Locative PP Interpretation                                                                   21
4.1    Projective and non-projective modification...........................     21
4.2    Boolean operations........................................     23
4.3    Plural reference objects   .....................................     26
5    On Directional Prepositions                                                                                                        27
6    Conclusions                                                                                                                                     33 A  Appendix: some useful definitions                                                                                             33
List of Figures
1        PP structure in X-bar Theory     .................................      4
2       notation for vectors and points.................................       6
3       non-convex objects     .......................................       8
4       V2 and V4 are boundary vectors of A     .............................       8
5       v is externally closest to A, w is not..............................       9
6       between A and B     ........................................     11
7       above x..............................................     11
8       beside x..............................................     12
9       inference (16) does not hold     ..................................     13
10      above is not point-monotone    ..................................     14
11      projective modification by ten meters..............................     22
12     a typical path for around   ....................................     29
List of Tables
1       typology of prepositions.....................................       3
2       upward vector-monotonicity     ..................................     17
3       relations between directional and locative prepositions....................     30
37