Two-Step Approaches to Natural Language Formalisms (Studies in Generative Grammar)
Contents
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . vii
I Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1 Desiderata for a linguistic formalism . . . . . . . . . . . . . 5
1.2 Logic, algebra and formal language theory . . . . . . . . . . 8
1.3 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Technical preliminaries . . . . . . . . . . . . . . . . . . . . . . 17
2.1 Alphabets, words and languages . . . . . . . . . . . . . . . 17
2.2 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3 Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
II The Classical Approach
Using MSO Logic as a Description Language for Natural
Language Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3 Model-theoretic syntax and monadic second-order logic . . . . 29
3.1 Overview of the classical approach . . . . . . . . . . . . . . 31
3.2 Monadic second-order logic . . . . . . . . . . . . . . . . . 31
3.2.1 Monadic second-order logic on trees . . . . . . . . . 32
3.2.2 An example language: L2K
,P . . . . . . . . . . . . . 36
3.2.3 Asmall example grammar . . . . . . . . . . . . . . 39
x Contents
4 Finite-state devices . . . . . . . . . . . . . . . . . . . . . . . . 43
4.1 Finite-state language processing . . . . . . . . . . . . . . . 44
4.1.1 Finite-state automata . . . . . . . . . . . . . . . . . 44
4.1.2 Finite-state transducer . . . . . . . . . . . . . . . . 47
4.2 Tree automata . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3 Tree-walking automata . . . . . . . . . . . . . . . . . . . . 53
4.4 Tree transducer . . . . . . . . . . . . . . . . . . . . . . . . 54
4.4.1 Top-downtree transducer . . . . . . . . . . . . . . . 54
4.4.2 Macro tree transducer . . . . . . . . . . . . . . . . 56
5 Decidability and definability . . . . . . . . . . . . . . . . . . . 58
5.1 Representing MSO formulas with tree automata . . . . . . . 58
5.2 Coding of relations . . . . . . . . . . . . . . . . . . . . . . 60
5.3 Constructing automata fromMSOformulas . . . . . . . . . 64
5.3.1 The decidability proof (various base steps) . . . . . 64
5.3.2 The decidability proof (inductive step) . . . . . . . . 68
5.3.3 Computational complexity . . . . . . . . . . . . . . 72
5.4 Finitemodel theory . . . . . . . . . . . . . . . . . . . . . . 73
5.5 Definability of relations in MSO logic . . . . . . . . . . . . 75
5.6 DefinableMSOtransductions . . . . . . . . . . . . . . . . . 80
5.7 Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.1 Parsingwithtree automata . . . . . . . . . . . . . . . . . . 85
6.2 Compiling grammatical principles to FSTAs . . . . . . . . . 88
6.3 Approximating P&Pgrammars . . . . . . . . . . . . . . . . 95
6.4 Some experimental results . . . . . . . . . . . . . . . . . . 98
6.5 Further applications . . . . . . . . . . . . . . . . . . . . . . 100
6.5.1 MSOlogic andCLP . . . . . . . . . . . . . . . . . 101
6.5.2 MSO logic as an automaton specification language . 103
6.5.3 Query languages . . . . . . . . . . . . . . . . . . . 104
6.5.4 Hardware verification . . . . . . . . . . . . . . . . . 104
6.5.5 Other MSO languages . . . . . . . . . . . . . . . . 105
7 Intermediate conclusion . . . . . . . . . . . . . . . . . . . . . 106
Contents xi
III Two Steps Are Better Than One
Extending the Use of MSO Logic to Non-Context-Free
Linguistic Formalisms . . . . . . . . . . . . . . . . . . . . . . . . 109
8 Overview of the two-step approach . . . . . . . . . . . . . . . 111
9 Non-context-freeness of natural language . . . . . . . . . . . . 115
9.1 Minimalist grammars . . . . . . . . . . . . . . . . . . . . . 115
9.2 Tree adjoining grammar . . . . . . . . . . . . . . . . . . . . 121
9.3 Linguistic motivation:v erb raising . . . . . . . . . . . . . . 124
10 The first step:L ifting . . . . . . . . . . . . . . . . . . . . . . . 131
10.1 Treegrammars . . . . . . . . . . . . . . . . . . . . . . . . 131
10.1.1 Context-free tree grammars . . . . . . . . . . . . . 134
10.1.2 Multiple context-free grammars . . . . . . . . . . . 140
10.2 Lifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
10.2.1 Lifting CFTGs . . . . . . . . . . . . . . . . . . . . 141
10.2.2 Lifting MCFGs . . . . . . . . . . . . . . . . . . . . 145
10.3 Coding the lifted structures . . . . . . . . . . . . . . . . . . 150
10.3.1 Tree automata . . . . . . . . . . . . . . . . . . . . . 151
10.3.2 MSOlogic . . . . . . . . . . . . . . . . . . . . . . 152
10.4 Summingup thefirst step . . . . . . . . . . . . . . . . . . . 153
11 The second step:R econstruction . . . . . . . . . . . . . . . . . 155
11.1 Reconstructing lifted (M)CFTGs . . . . . . . . . . . . . . . 156
11.1.1 Reconstruction with FSTWAs . . . . . . . . . . . . 158
11.1.2 ReconstructionwithMSOtransductions . . . . . . . 165
11.1.3 ReconstructionwithMTTs . . . . . . . . . . . . . . 166
11.2 Reconstructing lifted MCFGs . . . . . . . . . . . . . . . . . 169
11.2.1 Reconstruction with FSTWAs . . . . . . . . . . . . 173
11.2.2 ReconstructionwithMSOtransductions . . . . . . . 175
11.2.3 ReconstructionwithMTTs . . . . . . . . . . . . . . 176
11.3 Summaryof the two-step approach . . . . . . . . . . . . . . 180
xii Contents
IV Conclusion and Outlook . . . . . . . . . . . . . . . . . . . 183
12 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
13 Outlook . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
V Appendix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
A Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
B MONA code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194
B.1 XBarTheory . . . . . . . . . . . . . . . . . . . . . . . . . 194
B.2 Co-Indexation . . . . . . . . . . . . . . . . . . . . . . . . . 202
C Additional MSO Definitions . . . . . . . . . . . . . . . . . . . 207
C.1 The MSO Definition of Intended Dominance . . . . . . . . 207
D PrologCode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
D.1 Apply agivenMTTto a tree generated by anRTG . . . . . 209
D.2 TheExampleGrammars . . . . . . . . . . . . . . . . . . . 213
D.2.1 The CFTG Example: ΓL and MΓL . . . . . . . . . . 213
D.2.2 The TAG Example: ΓL
TAG and MΓL
TAG
. . . . . . . . . 214
D.2.3 The MCFG Example: G
MCFG and MG
MCFG
. . . . . . 215
Endnotes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
Mathematical Symbols . . . . . . . . . . . . . . . . . . . . . . . . 240
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243