\documentclass[a4paper,10pt]{llncs}

%%\usepackage{amssymb}

\title{\textsc{Categories, Constructions,  \\ and Dependency Relations}}
\author{Geert-Jan M. Kruijff}
\institute{Institute of Formal and Applied Linguistics\\
      Faculty of Mathematics and Physics\\
      Charles University, Prague\\[.5em]
      $\langle$\texttt{gj@cogsci.ed.ac.uk}$\rangle$}


\newcommand{\shortcite}[1]{\cite{#1}}

\begin{document}

\maketitle

\section{Introduction}

\noindent{}It is perhaps a geographical coincidence that one can draw
a more or less straight line connecting Brno, Prague, Amsterdam and
Edinburgh. But there are even more interesting connections to be
made. 

Edinburgh has been an important center of developments in categorial
grammar ever since the 1980's, side by side with Amsterdam where
categorial grammar was (re-)married to Montague grammar to give rise
to type-logical grammar; Prague has been a focal point of dependency
grammar and information structure ever since the beginning of
-already- last century, and Brno is the place where the spirit of
transparent intensional logic (TIL) is kept high.

It seems  that these approaches - dependency grammar,
transparent intensional logic, and type-logical grammars - all can be
considered to point to the following conception:

\begin{quotation}
\noindent\emph{The linguistically realized meaning of a sentence
  relates the use of words in the sentence as an \emph{expression} to
  the \emph{construction} of the sentence's (linguistic) meaning out
  of meanings of the individual words. }
\end{quotation}

The aim of this paper is to explore how these thre approaches could
possibly be combined. The advantages of a symbiosis of dependency
grammar, TIL, and categorial grammar or categorial type logics can be
briefly characterized as follows.  Categorial type logics provide us
with very powerful (formal \emph{and} computational) means to describe
intricate phenomena of surface structure, and using these logics to
construct a dependency-based perspective on natural language grammar
(DGL, \cite{GJ:diss}) enables us to model phenomena that arguably
cannot be explained using a phrase-structure based approach.
Furthermore, by using TIL we can tap into a considerable amount of
research in formal semantics, whereas for TIL, DGL might provide the
possibility for more fine-grained grammatical modeling.

\section{Three strands}

Dependency grammar, in its form as developed by Sgall et al
\shortcite{Sgall/etal:1986}, describes linguistic meaning using
dependency relations and the head/dependent distinction. Thus,
linguistic meaning as a \emph{representation} elucidates in a direct
way who modifies what, and in what semantically relevant way. Sgall et
al describe various types of dependency relations that can hold
between heads and dependents (see also Petkevi\v{c}'s
\cite{Petkevic:1995} for a succinct overview). For the representation it is assumed
that each dependent always has only one head (i.e. we are dealing with
trees), and that each relation between a head and a dependent is
classified as a \emph{single} dependency relation.\footnote{Observe
  that this is an \emph{assumption} - cf. Dowty's discussion on the
  closely related thematic relations or $\theta$-roles in
  \cite{Dowty:1989}.} Sgall et al, following Panevov\'a's
\cite{Panevova:1974}, describe (and distinguish)
dependency relations in terms of syntactic behavior. 

Categorial grammar, particularly in its extended form as
\emph{categorial type logics} combining resource-sensitive proof
systems with a typed $\lambda$-calculus (cf. work by Hepple
\shortcite{Hepple:IRCS}, Moortgat \shortcite{Moortgat:1996}, Morrill
\shortcite{Morrill:1994}, and Oehrle
\shortcite{Oehrle:1988,Oehrle:1994}), gives rise to the above
conception through the establishment of a Curry-Howard correspondence
between proof formulas and $\lambda$-terms. A proof is not (just) a
normative judgment - by virtue of the Curry-Howard correspondence, we
build a representation of the sentence's linguistic meaning \emph{in
  parallel} to establishing a syntactic structure, given the
sentence's outer form. It is interesting and important to note that
the $\lambda$-term representing linguistic meaning thus arrived at is
-without exception- considered to be the \emph{only} representation of
the sentence. Syntactic structure in the Chomskyan sense is a useful
but dispensible means to obtain our goal of relating the sentence's
outer form to its (conceivable) linguistic meaning - a point that, we
would argue, closely corresponds to the stress \cite{Sgall/etal:1986}
lays on representing a sentence in terms of its linguistic meaning. 

Finally, Tich\'y's transparent intensional logic as discussed
by Materna in \shortcite{Materna:1998}, describes meaning in terms of
type-logical ``constructions'' that show how a meaning is constructed
out of its components. A linguistic expression corresponds to a
construction, which in turn can be evaluated to an object. An
important characteristic is the distinction between constructions as
representations of meaning, and the objects they can be associated to.
Because we represent meaning as a \emph{construction}, and not as an
object, various semantical pitfalls are avoided. Moreover, the type
logic is defined on a ramified hierarchy, meaning we can talk not just
\emph{in terms of} constructions, but also \emph{about} constructions
(without needing a metalanguage). That enables us to give -for
example- a fairly straightforward logical account of propositional
attitudes.

Available literature has pointed out various parallels between the
above lines of thought. Categorial grammar and dependency grammar are
closely related, as for example Bar-Hillel and Bach frequently pointed
out. Montague Grammar and TIL have at occasion
been compared, the latter often being argued for as preferable over
the former - see for example Materna's \cite{Materna:1998}. And
finally, TIL has been used  in a couple of papers to provide a logical
interpretation of core aspects of the representations used in Sgall et
al's \cite{Sgall/etal:1986} - see for example
\cite{Materna/etal:1987,Svoboda/Materna:1987}.

Below we explore how we could try to weave these three lines of thought
together. As the starting point for our exploration we take Dependency Grammar
Logic (or DGL for short), as introduced in \cite{Kruijff:DGLintro} and
described in detail in \cite{GJ:diss}. DGL is a categorial type logic
that models dependency grammar, based on the intuitions behind the
framework described by Sgall et al.\footnote{Needless to say, space limits us in how far we can take our
exploration. For that reason, we will focus on pointing out the
possibilities rather than discussing formal details. Where possible we
will refer to places where such details are available.}  

\section{Dependency Grammar Logic}

DGL aims at describing the relation between a surface form and an
(underlying) linguistic meaning that can be considered as being
expressed by the outer form. The important questions there are of
course, \emph{how} form can be \emph{indicative} of linguistic
meaning, and what we consider to be the ingredients of linguistic
meaning that can be expressed by form.

Following \cite{Sgall/etal:1986}, the \emph{structure} of linguistic
meaning is phrased in terms of heads being modified by dependents,
along particular dependency relations. When establishing the relation
between surface form and linguistic meaning, we thus have to discern
words (or wordgroups) as  dependents and heads, making out what dependent modifies which
head and along which type of relation. As Jakobson, Mathesius, and
other authors in the Prague School have discussed at length (cf.
\cite{Panevova:1994,Vachek:1964}), \emph{case} can assist us in that
job (whereby we understand ``case'' to cover the various ways in which
morphological case is realized across languages -
cf. e.g. \cite{Croft:1990}, Chapter 2). 

However, there are more aspects of form that are indicative of the
underlying meaning of a sentence. For verbs, this concerns for example
modality, tense and aspect. Steedman presents in \cite{Steedman:POT}
an elaborate model of tense and aspect (a model which DGL
incorporates), explaining how tense and aspect give rise to
\emph{presuppositions} regarding relations holding between
the meaning of the sentence and the context. These relations need not
have to do primarily with temporality as such. Steedman advances the
point that the relations are more generally concerned with aspects
of causality and goal-directed action.   

Finally, there are aspects of form that are indicative of a
sentence's \emph{information structure}. These \emph{structural
  indications of informativity} \cite{Kruijff:DGLintro,GJ:diss}
signify how the meaning of a particular word (or wordgroup) is
dependent on the already established context, or how it will affect
that context (cf. Sgall et al's topic-focus articulation). 
Examples of structural indications are word order and intonation, cf. for example
\cite{Sgall/etal:1986,Steedman:SynProc}. 

To recapitulate, we understand \emph{form} here to be indicative of
how the meanings of words and wordgroups relate to one another
\emph{structurally}, and how they relate to the preceding context or
purport to affect the succeeding context. Dependency relations are
``presupposition triggers'' (in a loose sense of the
word)\footnote{Without any formal characterization of what a
  presupposition is, we can only use the idea of presupposition
  triggers here in the loose sense. Whether a dependency relation will
  trigger a genuine presupposition in the sense as used in formal semantics
  or a weaker form, i.e. an allegation, will be dependent on
  information structure - cf. the discussion
  in \cite{Sgall/etal:1986}. Note that in \cite{GJ:diss} I characterize
  dependency relations primarily from this `semantic' viewpoint, and
  conceive of syntactic behavior as derivated from that. On the
  contrary, Sgall et al characterize dependency relations (strictly)
  in terms of their syntactic behavior, without noting the influence
  that distinguishing different relations might have on a sentence's
  interpretation-in-context.}, just as tense and aspect signify
underlying presuppositions about e.g. causal relations. Finally, form
can be indicative of information structure.

Together this leads (in DGL) to an understanding of linguistic meaning
as a structure indicating how meanings of words are related using
dependency-relations, and how these meanings and their relations
\emph{project} presuppositions (and possibly, allegations) about
refering to the preceding context, affecting the succeeding context, and
presupposed temporal/causal/etc. relations. (See  \cite{GJ:diss} for
a detailed discussion.) The important point here is that, in keeping
with for example \cite{Sgall/etal:1986} and dynamic approaches like
Oehrle's \cite{Oehrle:1999}, we do not \emph{evaluate} the
presuppositions against the larger context. Linguistic meaning only
projects how, as far as the form has indicated it, the sentence ``aims to''
relate to the larger context. Whether it does (i.e. is felicitous) or
not, is left for subsequent discourse interpretation. 

In a sense this appears to correspond to TIL's distinction between
constructions and object - whereby DGL's linguistic meaning would
correspond to the former, and the interpretation established by
discourse interpretation could be considered to be like the latter. 

To be able to represent linguistic meaning, DGL uses
\emph{hybrid logics} \cite{Blackburn:Manifesto,Blackburn:ILD}.
Traditionally, typed $\lambda$-calculi are used to represent
``semantics'' in categorial grammar, cf. e.g.
\cite{Morrill:1994,Oehrle:1994}. As the above discussion already
indicates, though, our linguistic meaning potentially contains a rich
variety of information about modality, temporality, causality,
reference, etc. For this purpose, DGL abandons the fairly monolithic
traditional approach in favor for a system of modal logic that is
capable of capturing the kind of ontological richness we need.

\section{Weaving the three strands together}

In DGL, the underlying machinery for carrying out derivations
establishing the relation between form and meaning is phrased as a
resource-sensitive proof theory \cite{Moortgat:1996}. Traditionally,
categorial type logics relate form and meaning through a Curry-Howard
correspondence, established as follows. First, as Oehrle describes in
detail in \cite{Oehrle:1994}, the meanings of words are given in a
$(e,t)$-typed $\lambda$-calculus. These definitions are
translated into syntactic categories specifying the syntactic behavior
corresponding to the underlying meaning. Oehrle describes the
translation as an isomorphism - in particular, there is an isomorphic relation
between the number (and type) of arguments a verbal predicate takes
and the corresponding syntactic functional category. Besides an
isomorphism at the level of lexical meaning, there is also an
isomorphism (or at least, a close correspondence) at the level of
derivations. Fashioned after the original Curry-Howard isomorphism,
each step in a proof (operating on a category) is reflected in the
meaning. Thus, when we use natural deduction, composition (or
elimination) corresponds to application at the level of meaning, and
introduction corresponds to abstraction. 

It is easy to see why this has lead various authors to claim that surface syntax
is thus an artefact: this is a direct consequence of the
correspondence between lexically assigned categories and meanings, and
maintaining the correspondence between categories and meanings in a
derivation. 

Because DGL does not use a typed $\lambda$-calculus but a (many sorted
or hybrd) modal logic, a correspondence is established in a slightly
different fashion; namely, using a \emph{linking theory}. The purpose
of the linking theory is to relate dependency relations, specified in
a predicate's valency frame, with a surface category. Naturally, it is for
an important part based on the Praguian ideas about abstract case, how
abstract case realizes dependency relations, and how different
languages can realize case. The need for a more involved linking
theory (rather than saying that ``$e$'s map to N's'') arises from the
fact that we have a richer representation of meanings. At the same
time, we broadly maintain the ideas expressed in Oehrle's
\cite{Oehrle:1994} regarding the relation between categorial functions
and predicate structure\footnote{With some notable exceptions, as I
  noted in \cite{Kruijff:DGLintro}.}.

The way that we proceed in DGL to establish a relation between form
and meaning is very different from Hadacz's proposal involving TIL.
Hadacz discusses in \cite{Hadacz:TSD99} a so-called \emph{translation
  procedure} translating forms into TIL-constructions. Contrary to
DGL, syntactic composition appears to play little or no role in the
translation procedure (possibly because Hadacz' model is based on a
fragment of Czech that has a completely free word order). We would
like to argue that this makes the approach too restricted to be
generally applicable: For example, any phenomenon involving word order
will be hard to model, like case realized through word order (cf.
\cite{Croft:1990}), information structure, or restrictions on otherwise
flexible word order (like clitic placement in Czech). Hadacz' model
simply misses an explicit syntactic component. 

At the same time, it is not difficult to imagine how we can overcome this
problem, in almost exactly the same way as done in DGL. Like in DGL we
could establish a Curry-Howard correspondence - this time between
(primitive) objects and constructions in TIL on the one hand, and syntactic
categories on the other hand. 

\footnotesize{
\bibliography{engin}
\bibliographystyle{plain}
}
\end{document}




