Dependency Structures and Lexicalized Grammars: An Algebraic Approach

by Marco Kuhlmann (Editor)

Overview

Since 2002, FoLLI has awarded an annual prize for outstanding dissertations in the fields of Logic, Language and Information. This book is based on the PhD thesis of Marco Kuhlmann, joint winner of the E.W. Beth dissertation award in 2008. Kuhlmann’s thesis lays new theoretical foundations for the study of non-projective dependency grammars. These grammars are becoming increasingly important for approaches to statistical parsing in computational linguistics that deal with free word order and long-distance dependencies. The author provides new formal tools to define and understand dependency grammars, presents two new dependency language hierarchies with polynomial parsing algorithms, establishes the practical significance of these hierarchies through corpus studies, and links his work to the phrase-structure grammar tradition through an equivalence result with tree-adjoining grammars. The work bridges the gaps between linguistics and theoretical computer science, between theoretical and empirical approaches in computational linguistics, and between previously disconnected strands of formal language research.

Product Details

ISBN-13:	9783642145674
Publisher:	Springer Berlin Heidelberg
Publication date:	09/30/2010
Series:	Lecture Notes in Computer Science , #6270
Edition description:	2010
Pages:	137
Product dimensions:	6.10(w) x 9.25(h) x 0.36(d)

Table of Contents

1 Introduction 1

1.1 Motivation 1

1.1.1 Dependency Structures 1

1.1.2 Generative Capacity and Non-projectivity 3

1.2 Lexicalized Grammars Induce Dependency Trees 4

1.3 Overview of the Book 7

1.3.1 Dependency Structures 7

1.3.2 Dependency Languages 9

1.3.3 Contributions 10

2 Preliminaries 11

3 Projective Dependency Structures 17

3.1 Projectivity 17

3.1.1 Projectivity in the Sense of Harper and Hays 18

3.1.2 Projectivity in the Sense of Lecerf and Ihm 19

3.1.3 Projectivity in the Sense of Fitialov 19

3.1.4 Related Work 20

3.2 Algebraic Framework 20

3.2.1 Tree Traversal Strategies 21

3.2.2 Traversal of Treelet-Ordered Trees 23

3.2.3 Order Annotations 26

3.2.4 Dependency Algebras 26

3.3 Algorithmic Problems 28

3.3.1 Encoding and Decoding 28

3.3.2 Testing whether a Dependency Structure Is Projective 29

3.3.3 Related Work 29

3.4 Empirical Evaluation 30

3.4.1 The Projectivity Hypothesis 30

3.4.2 Experimental Setup 31

3.4.3 Results and Discussion 31

3.4.4 Related Work 32

4 Dependency Structures of Bounded Degree 33

4.1 The Block-Degree Measure 33

4.1.1 Blocks and Block-Degree 33

4.1.2 A Hierarchy of Non-projective Dependency Structures 35

4.1.3 Related Work 36

4.2 Algebraic Framework 37

4.2.1 Traversal of Block-Ordered Trees 38

4.2.2 Segmented Dependency Structures 40

4.2.3 Order Annotations 42

4.2.4 Dependency Structure Algebras 43

4.3 Algorithmic Problems 44

4.3.1 Encoding 44

4.3.2 Computing the Block-Degree of a Dependency Structure 48

4.4 Empirical Evaluation 48

5 Dependency Structures without Crossings 51

5.1 Weakly Non-projective Dependency Structures 51

5.1.1 Definition of Weak Non-projectivity 52

5.1.2 Relation to the Block-Degree Measure 53

5.1.3 Algebraic Opaqueness 54

5.1.4 Related Work 54

5.2 Well-Nested Dependency Structures 56

5.2.1 Definition of Well-Nestedness 56

5.2.2 Non-crossing Partitions 57

5.2.3 Algebraic Characterization 59

5.2.4 Testing whether a Dependency Structure Is Well-Nested 60

5.2.5 Related Work 60

5.3 Empirical Evaluation 61

6 Structures and Grammars 63

6.1 Context-Free Grammars 63

6.1.1 Definition 64

6.1.2 String Semantics 65

6.1.3 Linearization Semantics 66

6.1.4 Dependency Semantics 67

6.2 Linear Context-Free Rewriting Systems 68

6.2.1 Definition 69

6.2.2 String Semantics 70

6.2.3 Non-essential Concatenation Functions 71

6.2.4 Linearization Semantics 73

6.2.5 Dependency Semantics 74

6.2.6 Related Work 75

6.3 Coupled Context-Free Grammars 75

6.3.1 Definition 75

6.3.2 String Semantics 77

6.3.3 Dependency Semantics 78

6.3.4 Related Work 79

6.4 Tree Adjoining Grammar 79

6.4.1 Definition 80

6.4.2 Linearization Semantics 81

6.4.3 Related Work 82

7 Regular Dependency Languages 85

7.1 Regular Sets of Dependency Structures 85

7.1.1 Algebraic Recognizability 86

7.1.2 Elementary Properties 87

7.1.3 Regular Term Grammars 89

7.1.4 Regular Dependency Grammars 90

7.1.5 Dependency Languages and Lexicalized Grammars 92

7.2 Pumping Lemmata 93

7.2.1 The Pumping Lemma for Regular Term Languages 93

7.2.2 Ogden's Lemma for Regular Term Languages 95

7.3 Constant Growth 97

7.3.1 Constant Growth and Semilinearity 98

7.3.2 Regular Term Languages are Semilinear 100

7.3.3 Related Work 102

8 Generative Capacity and Parsing Complexity 103

8.1 Projection of String Languages 103

8.1.1 Labelled Dependency Structures 103

8.1.2 String-Generating Regular Dependency Grammars 105

8.1.3 String-Generative Capacity 105

8.2 String Languages and Structural Properties 107

8.2.1 Masked Strings 107

8.2.2 Enforcing a Given Block-Degree 108

8.2.3 Enforcing Ill-Nestedness 110

8.2.4 Hierarchies of String Languages 112

8.2.5 Related Work 113

8.3 Parsing Complexity 113

8.3.1 Membership Problems 113

8.3.2 The Standard Membership Problem 115

8.3.3 The Uniform Membership Problem 116

8.3.4 Recognition of Well-Nested Languages 119

8.3.5 Related Work 120

9 Conclusion 121

9.1 Main Contributions 121

9.2 Future Directions 121

9.2.1 Development of the Formalism 123

9.2.2 Linguistic Relevance 123

9.2.3 Applications to Parsing 124

9.2.4 An Algebraic Perspective on Grammar Formalisms 124

References 127

Index 135