Compositional Semantics in Verbmobil 
Johan Bos Bj~irn Gamb~ick Christian Lieske 
Yoshiki Mori Manfred Pinkal Karsten Worm 
Department of Computational Linguistics 
University of the Saarland 
Postfach 151150 
D-66041 Saarbrficken, Germany* 
e-mail : vm@coli .uni-sb.de 
Abstract 
The paper discusses how compositional 
semantics is implemented in the Verb- 
mobil speech-to-speech translation sys- 
tem using LUD, a description language 
for underspecified discourse representa- 
tion structures. The description lan- 
guage and its formal interpretation in 
DRT are described as well as its imple- 
mentation together with the architecture 
of the system's entire syntactic-semantic 
processing module. We show that a lin- 
guistically sound theory and formalism 
can be properly implemented in a sys- 
tem with (near) real-time requirements. 
1 Introduction 
Contemporary syntactic theories are normally 
unification-based and commonly aim at specifying 
as much as possible of the peculiarities of specific 
language constructions in the lexicon rather than 
in the "traditional" grammar rules. When doing 
semantic interpretation within such a framework, 
we want a formalism which allows for 
• compositionality, 
• monotonicity, and 
• underspecification. 
Compositionality may be defined rather strictly 
so that the interpretation of a phrase always 
should be the (logical) sum of the interpreta- 
tions of its subphrases. A semantic formalism 
being compositional in this strict sense would 
also trivially be monotonic, since no destructive 
*This research was funded by the German Federal 
Ministry of Education, Science, Research, and Tech- 
nology (BMBF) under grant number 01 IV 101 R. 
changes would need to be undertaken while build- 
ing the interpretation of a phrase from those of its 
subphrases) 
However, compositionality is more commonly 
defined in a wider sense, allowing for other 
mappings from subphrase-to-phrase interpreta- 
tion than the sum, as long as the mappings are 
such that the interpretation of the phrase still is a 
function of the interpretations of the subphrases. 
A common such mapping is to let the interpre- 
tation of the phrase be the interpretation of its 
(semantic) head modified by the interpretations 
of the adjuncts. If this modification is done by 
proper unification, the monotonicity of the for- 
malism will still be guaranteed. 
In many applications for Computational Lin- 
guistics, for example when doing semantically 
based translation -- as in Verbmobil, the German 
national spoken language translation project de- 
scribed in Section 2 -- a complete interpretation 
of an utterance is not always needed or even desir- 
able. Instead of trying to resolve ambiguities, for 
example the ones introduced by different possible 
scopings of quantifiers, the interpretation of the 
ambiguous part is left unresolved. The semantic 
formalism of such a system should thus allow for 
the underspecification of these unresolved ambi- 
guities (but still allow for them to be resolved in 
a monotonic way, of course). An underspecified 
form representing an utterance is then the rep- 
resentation of a set of meanings, all the possible 
interpretations of the utterance. 
The rest of the paper is structured as follows. 
Section 2 gives an overview of the Verbmobil 
Project. Section 3 introduces LUD (description 
Language for Underspecified Discourse 'represen- 
tations), the semantic formalism we use. Section 4 
compares our approach to that of others for simi- 
1 More formally, a semantic representation is mono- 
tonic iff the interpretation of a category on the right 
side of a rule subsumes the interpretation of the left 
side of the nile. 
131 
lar tasks. The actual implementation is described 
in Section 5, which also discusses coverage and 
points to some areas of further research. Finally, 
Section 6 sums up the previous discussion. 
2 The Verbmobil Project 
The project Verbmobil funded by the German 
Federal Ministry of Research and Technology 
(BMBF) combines speech technology with ma- 
chine translation techniques in order to develop 
a system for translation in face-to-face dialogues. 
The overall project is described in (Wahlster, 
1993); in this section we will give a short overview 
of the key aspects. 
The ambitious overall objective of the Verb- 
mobil project is to produce a device which will 
provide English translations of dialogues between 
German and Japanese businessmen who only have 
a restricted active, but larger passive knowledge of 
English. The domain is the scheduling of business 
appointments. The major requirement is to pro- 
vide translations as and when users need them, 
and do so robustly and in (near) real-time. 
In order to achieve this, the system is composed 
of time-limited processing components which on 
the source language (German or Japanese) side 
perform speech recognition, syntactic, semantic 
and pragmatic analysis, as well as dialogue man- 
agement; transfer on a semantic level; and on 
the target language (English) side generation and 
speech synthesis. When the users speak English, 
only keyword spotting for the dialogue manage- 
ment is undertaken. 
At any moment in the dialogue, a user may 
activate the Verbmobil device and start speak- 
ing his/her native language. The speech recog- 
nition component then processes the input and 
produces a word lattice representing the speech 
hypotheses and their corresponding prosodic in- 
formation. The parsing component processes the 
lattice and assigns each well-formed path through 
it one or several syntactic and (compositional) se- 
mantic representations. Ambiguities introduced 
by thesc may be resolved by a resolution compo- 
nent. The representations produced are then as- 
signed dialogue acts and used to update the model 
of the discourse, which in turn may be used by the 
speech recognizer to choose the current language 
model. The transfer component takes the (possi- 
bly resolved) semantic analysis of the input and 
builds a target language representation. The gen- 
erator then constructs the corresponding English 
expression. For robustness, this deep-level pro- 
cessing strategy is complemented with a shallow 
analysis-and-transfer component. 
3 Underspecified Representations 
3.1 Theoretical Background 
Since the Verbmobil domain is related to dis- 
course rather than isolated sentences, a variant 
of Kamp's Discourse Representation Theory, DRT 
(Kamp and Reyle, 1993) has been chosen as the 
model theoretic semantics. Itowcver, to allow for 
underspecification of several linguistic phenom- 
ena, we have chosen a formalism that is suited 
to represent underspecified structures: LUD, a 
description language for underspecified discourse 
representations (Bos, 1995). The basic idea is the 
one given in Section 1, namely that natural lan- 
guage expressions are not directly translated into 
Discourse Representation Structures (DRSs), but 
into a representation that describes several DRSs. 
Representations in LUD have the following dis- 
tinct features. Firstly, all elementary seman- 
tic "bits" (conditions, entities, and events) are 
uniquely labeled. This makes them easy to refer 
to and results in a very powerful description lan- 
guage. Secondly, meta variables over DRSs (which 
we call holes) allow for the assignment of under- 
specified scope to a semantic operator. Thirdly, 
a subordination relation on the set of holes and 
labels constrains the number of interpretations of 
the LUD-representation in the object language: 
DRSs. 
3.2 LUD-Representations 
A LUD-representation U is a triple 
< Hu,Lu,Cu > 
where Hu is a set of holes (variables over labels), 
Lu is a set of labeled (LUD) conditions, and Cu 
is a set of constraints. A plugging is a bijective 
function from holes to labels. For each plugging 
there is a corresponding DRS. The syntax of LUD- 
conditions is formally defined as follows: 
1. If x is a discourse marker (i.e., en- 
tity or event), then din(x) is a LUD- 
condition; 
2. If R is a symbol for an n-place rela- 
tion, xl,..., xn are discourse mark- 
ers, then pred(R, xl,...,x,~) is a 
LUD-condition; 
3. If I is a label or hole for a 
LUD-condition, then -~l is a LUD- 
condition; 
4. If 11 and 12 are labels (or holes) for 
LUD-conditions, then 11 --+ 12, 11AI2 
and 11 V 12 are LUD-conditions; 
5. Nothing else is a LUD-condition. 
132 
There are three types of constraints in LUD- 
representations. There is subordination (<_), strict 
subordination (<), and fimdly presupposition (c~). 
These constraints are syntactically defined as: 
If/i, l.~ are labels, h is a hole, then It < h, 
11 < 12 and l~ ~ 12 are LUD-constraints. 
The interpretation of a LUD-representation is 
the interpretation of top, the label or hole of a 
LUi)-representation tbr which tt,ere exists no label 
thai; subordinates it. ~ 
The interpretation fnnction I is a function from 
a labeled condition to a DRS. This hmction is de- 
fined with respect to a plugging P. We represent a 
I)RS ~ a box ~DI~ , where D is the set of dis- 
course markers and C is the set of conditions. The 
mappings between LUD-conditions and I)RSs are 
then detiued in (2)-(9) where l is a label or hole 
and ~b is a labeled condition. 
I(~) ifr l: ~b ~ Lu 
5,(0 = (u) 
iirl c Hu 
= (3) 
\[(pT,(;a(~,Xl,... ,xn) ) = (~1) 
{\[ ,.(.., ,<\]} 
:(t, A l=) = (s) 
:(l, = (6) 
{ L i 'I~'1 ~I(ll)&~ K2~I(l'2)} 
v l.,.) = (r) 
{1 \[ KI V/f2\] \[I£l~ I(11)& f£2 ~ /(12)} 
I(-,11) = (8) 
\[n (6) ® is the merge operation, that takes two 
DRSs K1 and K= and returns a I)RS which do- 
main is the nnion of the set of the domains of K1 
and K2, and which conditions form the union of 
the set of the conditions of K1 and K2. 
2q.'he reade.r interested in a more detailed discus- 
SiGn of the iul;erl)retation of underspccified semanti(: 
representations is referred to (Bos, 19{)5). 
3.3 Lexical Entries and Composition 
For building LUD-reprcsentations we use a 
lambda-operator and functional application in 
order to compositionally combine simple LUD- 
representations to complex ones. In addition, we 
have two functions that help us to keep track 
of the right labels. These are top, as described 
above, and main, the label of the semantic head of 
a LU1)-reprcsentation. Further, we have an opera- 
tion that combines two LUD-representations into 
one: q) (merge for LUl)-representations). Some 
sample lexical entries for German as well as a sam- 
ple derivation, are shown in Figure 1. 
4 Related Work 
The LUD representation is quite closely related to 
UDI{Ss, underspecified l)t{Ss (Reyle, 1993). The 
main difference is that the I,UI) description lan- 
guage in principle is independent of the object 
langnage, thus not only DI{T, but also or(tinary 
predicate logic, as well as a Dynamic Predicate 
Logic (Groenendijk and Stokhof, 1991) can be 
used as the object language of LUI), as shown 
in (Bos, 1995). Compared to UDRS, LUD also 
has a stronger descriptive power: Not DRSs, but 
the smallest possible semantic components are 
uniquely labeled. 
The Verbmobil system is a translation system 
built by some 30 different groups in three coun- 
tries. The semantic \[brmalism used on the En- 
glish generation side has been developed by CSLI, 
Stanford and is called MRS, Minimal Recursion 
Semantics (Copest;ake eL al., 1995). The deep-- 
level syntactic and semalttic German processing of 
Verbmobil is also done along two parallel paths. 
The other path is developed by IBM, lleidelberg 
and uses a variant of MRS, Underspecified Min- 
imal Recnrsion Semantics (UMRS) (Egg and Le- 
beth, 1995). All the three formalisms LUD, MRS, 
and UMRS have in common that they use a fiat, 
nco-Davidsoniau representation and allow for the 
nndcrspecification o\[" functor-argmnent relations. 
In MRS, this is done by unification of the rela- 
tions with unresolved dependencies. This, how- 
ever, results in structures which cannot be fltrther 
resolved. In UMRS this is modified by expressing 
the scoping possibilities directly as disiunctions. 
The main difference between both types of MRSs 
and LUI) is that the interpretation of LUI) in 
an object language other than ordinary predicate 
logic is well delined, as described in Section 3.2. 
The translation task of the SICS-SRI l:/ilin-- 
gnal Conversation Interpreter, BCI (Alshawi et 
al., 1991) is quite similar to that of Verbmobil. 
The BCI does translation at the level of Quasi- 
13 3 
das : 
geht : 
AP. < { },{ l, : dm(z) },{ li w main(P) } >@P(z) 
ll : pred(gehen, e), ) 
Ay e < { h, }, l :pre (the..e,e,y), ,{ Zk < h, } > 
lk : li A lj 
jeder : AP.AQ. < { hi } lk : lj A maln(P), It < top(Q), ' ' main(Q) < hi 
11 : lk -4 hi 
termin : Ax. < { },{ li :termin(x) },{ } > 
15 pred(gehen, e), 17 < ho, > 
das geht : Ae. < { ho }, 16 pred(theme,e,z), ' 14 ~i 17 
lz 15 A 16 
> @P(z) @ Q(z) 
Figure 1: Lexical entries and a sample derivation in LUD 
Logical Form, QLF which also is a monotonic 
representation language for compositional seman- 
tics as discussed in (Alshawi and Crouch, 1992). 
The QLF formalism incorporates a Davidsonian 
approach to semantics, containing underspecified 
quantifiers and operators, as well as 'anaphoric 
terms' which stand for entities and relations to be 
determined by reference resolution. In these re- 
spects, the basic ideas of the QLF formalism are 
quite similar to LUD. 
5 Syntax-Semantics Interface and 
Implementation 
5.1 Grammar 
The LUD semantic construction component has 
been implemented in the grammar formalism 
TUG, Trace and Unification Grammar (Block and 
Schachtl, 1992), in a system called TrUG (in coop- 
eration with Siemens AG, Munich, who provided 
the German syntax and the TrUG system). TUG 
is a formalism that combines ideas from Gov- 
ernment and Binding theory, namely the use of 
traces, with unification in order to account for, for 
example, the free word order phenomena found in 
German. 
5.1.1 Syntax and Semantics 
A TUG grammar basically consists of PATR-II 
style context free rules with feature annotations. 
Each syntactic rule gets annotated with a seman- 
tic counterpart. In this way, syntactic derivation 
and semantic construction are fully interleaved 
and semantics can further constrain the possible 
readings of the input. 
In order to make our formalisation executable, 
we employ the TrUG system, which compiles our 
rules into an efficient Tomita-style parser. In addi- 
tion TrUG incorporates sortal information, which 
is used to rank parsing results. 
Consider a simplified example of a syntactic rule 
annotated with a semantic functor-argument ap- 
plication. 
s ---> rip, vp l 
np:agr = vp:agr• 
lud_fun arg ( s, vp, np). 
In this example, a sentence s consists of an np 
and a vp. The first feature equation annotated to 
this rule says that the value of the feature agr (for 
agreement) of the np equals that of the respective 
feature value of the vp. 
5.1.2 The Composition Process 
A category symbol like np in the rule above also 
stands for the entry node of its associated feature 
structure. This property is used for the seman- 
tic counterpart of the rule: lud..fun_.arg is a call 
to a semantic rule, a macro in the TUG nota- 
tion, which defines functor-argument application. 
Since the macro gets the entry nodes of the fea4 
ture structures as arguments, all the information 
present in the feature structures can be accessed 
within the macro which is defined as 
lud_fun_arg(Result,Fun,hrg) => 
lud_ cont ext_equal (Fun, Result ), 
context (Fun, FunContext), 
context (hrg, ArgCont ext ), 
subcat (Result, ResultSc), 
subcat (Fun, \[hrgContext \] ResultSc\] ). 
134 
The functor-argument application is based on 
the notion of the context of a LUD-representation. 
The context of a LUD-representation is a 
three-place structure consisting of the LUD- 
representation's main label and top hole (as de- 
scribed in Section 3.3) and its main instance, 
which is a discourse marker or a lambda-bound 
variable. A LUD-representation also has a seman- 
tic subcategorization list under the feature subcat 
which performs the same function as a A-prefix. 
This list consists of the contexts of the arguments 
a category is looking for. 
The functor-argumcnt application macro thus 
says the following. The context of the result is 
the context of the functor. The functor is look- 
ing for the argument as the first element on its 
subcat list, while the result's subcat list is that of 
the functor minus the argument (which has been 
bound in the rule). The binding of variables be- 
tween functor and argument takes place via the 
subcat list, through which a functor can access 
the main instance and thc main label of its argu- 
ments and state relations between them. 
Note that the only relevant piece of informa- 
tion contained in a LUD-representation for the 
purpose of composition is its context. Its content 
in terms of semantic prcdicates is handled differ- 
ently. The predicates of a LUD-representation are 
stored in a special slot provided for each category 
by the TrUG systcm. The contents of this slot 
is handed up the tree from the daughters to the 
mother completely monotonically. So the predi- 
cates introduced by some lexical entry percolate 
up to the topmost node automatically. 
These two restrictions, the use of only a LUD- 
representation's context in composition and the 
monotonic percolation of semantic predicates up 
the tree, make the system completely composi- 
tional in the sense defined in Section 1. 
5.1.3 The lexicon 
To see how the composition interacts with the 
lexicon, consider the following lexical macro defin- 
ing the semantics of a transitive verb 
trans_verb_sem(Cat,Rel,\[Rolel,Role2\]) => 
basic_pred(Rel,Inst,Ll), 
udef(Inst,L2), 
group(\[L1,L2,ArgLI,ArgL2\],Main), 
leq(Main,Top), 
lud_context(Cat,Inst,Main,Top). 
role(Inst,Rolel,Argl,ArgL1), 
role(Inst,Role2,Arg2,ArgL2), 
subcat(Cat,\[lud(Argl .... ), 
lud(Arg2 .... )\] ). 
The macro states that a transitive verb in- 
troduces a basic predicate of a certain relation 
with an instance and a label. The instance is 
related to its two arguments by argument roles. 
The arguments' instances are accessed via the 
verb's subcat list (and get bound during functor- 
argument application, cf. above). The labels in- 
troduced are grouped together; the group label is 
the main label of the LUD-representation, the in- 
stance its main instance. Another property of the 
verb's semantics is that it introduces the top hole 
of the sentence. 
5.2 Interfaces to Other Components 
As sketched in Section 2, our semantic construc- 
tion component delivers output to the components 
for semantic evaluation and transfer. The para- 
graphs that follow describe the common interface 
to these two components. 
5.2.1 Resolution of Underspecification 
Generating a scopally resolved LUD-represen- 
tation from an underspecified one is the process 
which we referred to as plugging in Section 3.2. 
It aims at making the possibly ambiguous se- 
mantics captured by a LUD unique. Obviously, 
purely mathematical approaches for transforming 
the partial ordering encoded in the leq constraints 
into a total ordering may yield many results. 
Fortunately, linguistic constraints allow us to 
reduce the effort that has to be put into the com- 
putation of pluggings. An example is the linguis- 
tic observation that a predicate that encodes sen- 
tence mood in many cases modifies all of the re- 
mainder of the proposition for a sentence. Thus, 
pluggings where the predicate for sentence mood 
is subject to a leq constraint should not be con- 
sidered. They would result in a resolved structure 
expressing that the mood-predicate does not have 
scope over the remaining proposition. This would 
be contrary to the linguistic observation. 
5.2.2 Supplementary Information 
As a supplement to semantic predicates, our 
output contains various kinds of additional infor- 
mation. This is caused by the overall architec- 
ture of the Verbmobil system which does not pro- 
vide for fully-interconnected components. There 
is, e.g., no direct connection between the speech 
recognizer and the component for semantic eval- 
uation. Thus, our component has to pipe certain 
kinds of information (like prosodic values). Ac- 
cordingly, our output consists of "Verbmobil In- 
terface Terms" (VITs), which differ slightly from 
the LUD-terms described above mainly in that 
they include non-semantic information. 
135 
5.3 Implementation Status 
Currently, the lexicon of the implemented system 
contains about 1.400 entries (full forms) and the 
grammar consists of about 400 syntactic rules, 
of which about 200 constitute a subgrammar for 
temporal expressions. The system has been tested 
on three simplified dialogues from a corpus of spo- 
ken language appointment scheduling dialogues 
collected for the project and processes about 90% 
of the turns the syntax can deal with. 
The system is currently being extended to cover 
nine additional dialogues from the corpus com- 
pletely. The size of the lexicon will then be about 
2500 entries, which amounts to about 1700 lem- 
mata. 
6 Conclusions 
We have discussed the implementation of a com- 
positional semantics in the Verbmobil speech-to- 
speech translation system. The notions of mono- 
tonicity and underspecification were discussed 
and LUD, a description language for underspeci- 
fled discourse representation structures was intro- 
duced. As shown in Section 3, the LUD descrip- 
tion language has a well-defined interpretation in 
DRT. Differently from Reyle's UDRSs, however, 
LUD assigns labels to the minimal semantic ele- 
ment and may also be interpreted in other object 
languages than DRT. 
The key part of the paper, Section 5, showed 
how the linguistically sound LUD formalism has 
been properly implemented in a (near) real-time 
system. The implementation in Siemens' TUG 
grammar formalism was described together with 
the architecture of the entire semantic processing 
module of Verbmobil and its current coverage. 
7 Acknowledgements 
We are gratefully emdebted to Scott McGlashan 
and CJ Rupp who both worked on parts of the 
implementation. The results of the paper have 
greatly benefitted from the cooperation with our 
other collegues in Verbmobil, especially those at 
IBM and CSLI, as well as the ones working on the 
modules closest to ours in the processing chain. 
A number of people have contributed directly to 
parts of the work described in the paper: Ronald 
Bieber, Hans-Ulrich Block, Michael Dorna, Man- 
fred Gehrke, Johannes Heinecke, Julia Heine, 
I)aniela Kurz, Elsbeth Mastenbroek, Sebastian 
Millies, Adam Przepiorkowski, Stefanie Schachtl, 
Michael Schiehlen, Feiyu Xu, and several others. 
References 
Hiyan Alshawi and Richard Crouch. 1.992. Mono- 
tonic semantic interpretation. In Proceedings 
of the 30th Annual Meeting of the Association 
for Computational Linguistics, pages 32-39, 
Newark, Delaware, June. ACL. Also available 
as SRI International Technical Report CRC- 
022, Cambridge, England. 
Hiyan Alshawi, David M. Carter, Bj6rn Gamb£ck, 
and Manny Rayner. 1991. Translation by 
Quasi Logical Form transfer. In Proceedings of 
the 29th Annual Meeting of the Association for 
Computational Linguistics, pages 161-168, Uni~ 
versity of California, Berkeley, California, July. 
ACL. Also available as SRI International Tech- 
nical Report CRC-021, Cambridge, England. 
Hans Ulrich Block and Stefanie Schachtl. 1992. 
Trace and Unification Grammar. In Proceed- 
ings of the 1.~th International Conference on 
Computational Linguistics, volume 2, pages 
658-664, Nantes, France, July. ACL. 
Johan Bos. 1995. Predicate logic unplugged. 
In Proceedings of the 10th Amsterdam Collo- 
quium, University of Amsterdam, Amsterdam, 
Holland. 
Ann Copestake, Dan Flickinger, Rob Malouf, Su- 
sanne Riehemann, and Ivan Sag. 1995. Trans- 
lation using Minimal Recursion Semantics. Ms., 
Stanford University, Stanford, California. 
Markus Egg and Kai Lebeth. 1995. Semantic un- 
derspecification and modifier attachment ambi- 
guities. In Proceedings of the Annual Meeting 
of the German Linguistic Society, University of 
Diisseldorf, Diisseldorf, Germany. 
Jeroen Groenendijk and Martin Stokhof. 1991. 
Dynamic Predicate Logic. Linguistics and Phi- 
losophy, 14:39-100. 
Hans Kamp and Uwe Reyle. 1993. From Dis- 
course to Logic: An Introduction to Modelthe- 
oretic Semantics of Natural Language, Formal 
Logic and DRT. Kluwer, Dordrecht, Ifolland. 
Uwe Reyle. 1993. Dealing with ambiguities by un- 
derspecification: Construction, representation 
and deduction. Journal of Semantics, 10:123-- 
179. 
Wolfgang Wahlster. 1993. Verbmobil: Trans- 
lation of face-to-face dialogs. In Proceed- 
ings of the 3rd European Conference on Speech 
Communication and Technology, pages 29-38, 
Berlin, Germany, September. 
1.36 
