Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

A Mathematical Formalism for
Linguistic Theories
with an Application in
Head-Driven Phrase Structure
Grammar
Frank Richter
Philosophische Dissertation
angenommen von der Neuphilologischen Fakultat
der Universitat Tubingen
am 23. Juni 2000
Tubingen
2000Gedruckt mit Genehmigung der Neuphilologischen Fakultat
der Universitat Tubingen
Hauptberichterstatter: Prof. Dr. Erhard W. Hinrichs
1. Mitberich Prof. Dr. Uwe Monnich
2. Mitberichterstatter: Priv. Doz. Dr. Fritz Hamm
3. Mitberich Prof. Carl Pollard, Ph.D. (Columbus, Ohio, USA)
Dekan Prof. Dr. Bernd EnglerContents
Acknowledgments 1
1 Introduction 4
1.1 A Formal Framework for Linguistic Theories . . . . . . . . . . 7
1.2 Linguistic Analyses . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Contribution of this Research . . . . . . . . . . . . . . . . . . 12
2 Formal Foundations I 15
2.1 Language as Partial Information . . . . . . . . . . . . . . . . . 22
2.1.1 The Idea . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.1.2 Formal Reconstruction . . . . . . . . . . . . . . . . . . 27
2.1.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.2 Language as a Collection of Total Objects . . . . . . . . . . . 71
2.2.1 The Idea . . . . . . . . . . . . . . . . . . . . . . . . . . 73
2.2.2 Formal Reconstruction and Di eren t Perspectives . . . 75
2.2.2.1 SRL . . . . . . . . . . . . . . . . . . . . . . . 76
2.2.2.2 Exhaustive Models . . . . . . . . . . . . . . . 89
2.2.2.3 Types and Tokens . . . . . . . . . . . . . . . 106
2.2.2.4 Strong Generative Capacity . . . . . . . . . . 120
2.2.3 Problems: Missing Concepts . . . . . . . . . . . . . . . 134
3 Formal Foundations II: RSRL 150
3.1 The Formalism . . . . . . . . . . . . . . . . . . . . . . . . . . 152
3.1.1 The Description Language . . . . . . . . . . . . . . . . 155
3.1.2 Constructing a Canonical Exhaustive Model . . . . . . 181
3.1.2.1 Congruence and Indiscernibility . . . . . . . . 182
3.1.2.2 Morphs and Morph Admission . . . . . . . . 186
3.1.2.3 Canonical Exhaustive Models . . . . . . . . . 196
iiiiv CONTENTS
3.1.3 The Di eren t Perspectives Revisited . . . . . . . . . . 205
3.2 A Notation for Linguistics . . . . . . . . . . . . . . . . . . . . 211
3.2.1 An AVM Syntax for RSRL . . . . . . . . . . . . . . . . 212
3.2.2 Equivalence to RSRL Syntax . . . . . . . . . . . . . . 216
3.2.3 Abbreviatory Conventions . . . . . . . . . . . . . . . . 225
3.3 Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
4 The Grammar of Pollard & Sag 94 245
4.1 Quanti cation . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
4.2 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249
4.3 Chains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
4.3.1 An Example . . . . . . . . . . . . . . . . . . . . . . . . 259
4.3.2 On the Status of Chains in Grammars . . . . . . . . . 270
4.3.3 Relations between and Lists . . . . . . . . . . . 278
4.4 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 279
4.4.1 A Problem and a Solution . . . . . . . . . . . . . . . . 279
4.4.2 Notation and Examples . . . . . . . . . . . . . . . . . 291
4.4.3 Application . . . . . . . . . . . . . . . . . . . . . . . . 297
4.5 Parerga and Paralipomena . . . . . . . . . . . . . . . . . . . . 304
4.5.1 An Apparently Problematic Principle . . . . . . . . . . 304
4.5.2 Parametric Sorts . . . . . . . . . . . . . . . . . . . . . 310
4.5.3 The Lexicon and Lexical Rules . . . . . . . . . . . . . 315
5 Beyond Classical HPSG 320
5.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321
5.2 Meurers 2000 and Przepi orkowski 1999a . . . . . . . . . . . . 324
5.2.1 Case Theory . . . . . . . . . . . . . . . . . . . . . . . . 325
5.2.2 Quanti er Retrieval . . . . . . . . . . . . . . . . . . . . 331
5.2.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 335
5.3 Linearization . . . . . . . . . . . . . . . . . . . . . . . . . . . 336
5.3.1 The Architecture . . . . . . . . . . . . . . . . . . . . . 336
5.3.2 Topological Relations and Principles . . . . . . . . . . 342
5.3.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 349
5.4 Model-theoretic Semantics . . . . . . . . . . . . . . . . . . . . 350
5.4.1 A Grammar of the Syntax of Ty2 . . . . . . . . . . . . 352
5.4.2 An Operational Extension . . . . . . . . . . . . . . . . 363
5.4.3 A Principle at the Syntax-Semantics Interface . . . . . 369
5.4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . 372CONTENTS v
A Proof: Existence of Exhaustive Models 374
A.1 A Di eren t Characterization . . . . . . . . . . . . . . . . . . . 374
A.2 Existence Proof for Exhaustive Models . . . . . . . . . . . . . 382
B Proof: AVM Syntax for RSRL 404
C The Principles of Pollard & Sag 94 419
Bibliography 436Acknowledgments
It was in spring 1992 when I rst came into contact with HPSG, and from
the very beginning, my thinking about HPSG was associated with the four
people who had the most profound in uence on this thesis. Tilman Hohle,
who taught me almost everything I know about syntax, had decided to give
his rst seminar on HPSG. The idea was that we would read the manuscript
of what was to become Pollard and Sag 1994 in class, and try to understand
this relatively new linguistic framework. For me, this became an obsession
for years. Paul King, who can turn a lecture on logic into one of the most
exciting events on earth, had just come from Stanford to Tubingen and taught
the rst of many classes to come on the formalization of HPSG. Despite his
enormous e orts, I did not understand much in that rst seminar, and it
most certainly was not his fault. In the same semester, Carl Pollard visited
Tubingen and gave a few lectures in Tilman Hohle’s seminar. I still vividly
remember the moment when they rst met. And, as always, Manfred Sailer
was in the same classes as I was, and we spent hours together laughing and
wondering about the strange ways of linguistic theories. From our rst years
at university, when we did our computer science assignments together, right
through to our latest joint papers, we have been working side-by-side, and we
hope the tradition continues. Manfred is a wonderful person, a great friend,
and I cannot imagine what life would be like without him. Thank you for
your friendship, Manfred!
Without Tilman Hohle, Manfred, Paul, and Carl, this thesis would never
have been written. They were always a part of the project, they never stopped
asking questions, and they never let me get away with cheap answers. I hope
that they look kindly on what I did with their ideas and suggestions.
In spring 1995, I joined the HPSG project(s) of the SFB 340, which at the
time included Thilo Gotz, Detmar Meurers, Guido Minnen, and Manfred.
Detmar’s enthusiasm for everything having to do with linguistics and his
readiness to help with any kind of problem in any way he possibly can made
even the most stressful times bearable. Thilo tried very patiently to explain
to me over and over again what a relational extension of a constraint language
is and what a feature constraint grammar means. I hope I understood at least
some of what he was trying to explain.
In 1996, Gerald Penn came to join our HPSG group. It is impossible
to express how much I learned from him, and the ideas that Manfred and I
discussed with him about constructing a comprehensive formalism for HPSG
1were strengthened immeasurably thanks to his rigorous and uncompromising
standards. No single little detail remained unquestioned. Thank you, Ger-
ald, for becoming such a good friend, for those long evenings of stimulating
conversations about linguistics, mathematical formalisms, philosophy, and
everything else! I miss you a lot now you’ve left Tubingen, and I hope that
we can stay in touch despite the ocean that lies between us now.
Sometime in 1998, I had the pleasure of reading the rst linguistics paper
that was formalized in RSRL. Adam Przepi orkowski became the rst linguis-
tic user, he kept pressing me to make RSRL as user-friendly as I could, and
to make an extra e ort to explain mathematical concepts in linguistic terms.
As an invaluable proofreader of many papers, he spotted more mistakes than
ever should have existed. But I also fondly remember our long non-linguistic
conversations, especially that night in Edinburgh when we were standing
outside in the cold summer air of Scotland.
Uwe Monnich gave me the opportunity to present an early version of
RSRL in his reading group that included Tom Cornell, Hans-Peter Kolb,
and Frank Morawietz, all of whom gave valuable comments and made me
aware of many problems that I had missed. I have greatly bene ted from
comments from and discussions with Mike Calcagno, Bob Carpenter, Thilo
Gotz, Erhard Hinrichs, Bob Kasper, Stephan Kepser, Valia Kordoni, Kai-
Uwe Kuhnberger, Detmar Meurers, Guido Minnen, Uwe Monnich, Sascha
Rosen, Kiril Simov, Jesse Tseng, and Shuly Wintner. I also learned a lot
from the students in my seminars, from the audiences at various conferences
Manfred and I went to in the past few years, and from many friends and
colleagues at the Seminar fur Sprachwissenschaft in Tubingen.
Even in the nal stages of writing a dissertation, there is some life outside
of work. The daily lunch at the Mensa was one of the things that helped me
to get through the hard times at the end, and I would like to thank Frederik
Fouvry, Valia Kordoni, Ania Kupsc, Gergana Popova, and Jesse Tseng for
all the fun we had together.
I am especially grateful to the current members of the HPSG project,
Frederik Fouvry, Kordula De Kuthy, Beata Trawinski, and Jesse Tseng for
putting up with somebody who in the last few months was hardly contribut-
ing anything. I am also indebted to the members of the Tubingen/So a
CLaRK program, Gergana Popova, Atanas Kiryakov, Ania Kupsc, and Kiril
Simov, for their patience with me.
My sincere gratitude goes to the research assistants of the project, Michael
Auth, Doris Penka, Christian Richard, and Holger Wunsch, who helped me
2in many ways and made staying focused on work so much easier. Our system
administrator, Jochen Saile, provided much-needed technical support. Our
secretaries, Rosemary Drescher and Stephanie Schwarz, kept the paperwork
under control and were always ready to help with the mysteries of university
administration and budgets.
I would not have been able to write this dissertation without the constant
support of my family, Gertrud, Horst, and my grandmother. Finally, and
most importantly, I thank Janina for her patience, love, and understanding.
3Chapter 1
Introduction
Some modern linguistic theories in the tradition of early generative grammar
aspire to share a high degree of formalization with those sciences that are
traditionally known as the \exact" sciences, such as chemistry and physics.
As the linguistic descriptions in grammars of natural languages become more
and more elaborate, as the grammars themselves become more and more com-
prehensive, and as e orts to make use of these grammars in computational
applications of language processing persist, the techniques of mathematics
turn out to be an indispensable means of ensuring the internal coherence of
large grammars and of expressing them with unambiguous clarity. Without
the helping hand of mathematics, it would be impossible to pin down exactly
what the empirical predictions of even a moderately comprehensive grammar
are, but without knowing the exact predictions of a grammar, it is hard to
see how a grammar could be falsi ed according to criteria that go beyond
aesthetic preferences; and any attempt at a computational modeling of the
grammar would need to cope with not having a clearly de ned target.
It is no surprise, then, that the need for grammatical frameworks that
possess a well-de ned semantics was recognized a long time ago even outside
theoretical linguistics when alternatives to context free grammars and aug-
mented transition networks became widely used in computational linguistics.
Whereas the traditional formalisms had a semantics, the new frameworks
that were designed to be better suited for developing large grammars did
not. Pereira and Shieber 1984 summarizes the potential problems with an
informal grammatical framework concisely:
In the absence of a rigorous semantics for a given grammar for-
4

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin