Introduction / 1: |
Motivation / 1.1: |
Dependency Structures / 1.1.1: |
Generative Capacity and Non-projectivity / 1.1.2: |
Lexicalized Grammars Induce Dependency Trees / 1.2: |
Overview of the Book / 1.3: |
Dependency Languages / 1.3.1: |
Contributions / 1.3.3: |
Preliminaries / 2: |
Projective Dependency Structures / 3: |
Projectivity / 3.1: |
Projectivity in the Sense of Harper and Hays / 3.1.1: |
Projectivity in the Sense of Lecerf and Ihm / 3.1.2: |
Projectivity in the Sense of Fitialov / 3.1.3: |
Related Work / 3.1.4: |
Algebraic Framework / 3.2: |
Tree Traversal Strategies / 3.2.1: |
Traversal of Treelet-Ordered Trees / 3.2.2: |
Order Annotations / 3.2.3: |
Dependency Algebras / 3.2.4: |
Algorithmic Problems / 3.3: |
Encoding and Decoding / 3.3.1: |
Testing whether a Dependency Structure Is Projective / 3.3.2: |
Empirical Evaluation / 3.3.3: |
The Projectivity Hypothesis / 3.4.1: |
Experimental Setup / 3.4.2: |
Results and Discussion / 3.4.3: |
Dependency Structures of Bounded Degree / 3.4.4: |
The Block-Degree Measure / 4.1: |
Blocks and Block-Degree / 4.1.1: |
A Hierarchy of Non-projective Dependency Structures / 4.1.2: |
Traversal of Block-Ordered Trees / 4.1.3: |
Segmented Dependency Structures / 4.2.2: |
Dependency Structure Algebras / 4.2.3: |
Encoding / 4.3: |
Computing the Block-Degree of a Dependency Structure / 4.3.2: |
Dependency Structures without Crossings / 4.4: |
Weakly Non-projective Dependency Structures / 5.1: |
Definition of Weak Non-projectivity / 5.1.1: |
Relation to the Block-Degree Measure / 5.1.2: |
Algebraic Opaqueness / 5.1.3: |
Well-Nested Dependency Structures / 5.1.4: |
Definition of Well-Nestedness / 5.2.1: |
Non-crossing Partitions / 5.2.2: |
Algebraic Characterization / 5.2.3: |
Testing whether a Dependency Structure Is Well-Nested / 5.2.4: |
Structures and Grammars / 5.2.5: |
Context-Free Grammars / 6.1: |
Definition / 6.1.1: |
String Semantics / 6.1.2: |
Linearization Semantics / 6.1.3: |
Dependency Semantics / 6.1.4: |
Linear Context-Free Rewriting Systems / 6.2: |
Non-essential Concatenation Functions / 6.2.1: |
Coupled Context-Free Grammars / 6.2.4: |
Tree Adjoining Grammar / 6.3.1: |
Regular Dependency Languages / 6.4.1: |
Regular Sets of Dependency Structures / 7.1: |
Algebraic Recognizability / 7.1.1: |
Elementary Properties / 7.1.2: |
Regular Term Grammars / 7.1.3: |
Regular Dependency Grammars / 7.1.4: |
Dependency Languages and Lexicalized Grammars / 7.1.5: |
Pumping Lemmata / 7.2: |
The Pumping Lemma for Regular Term Languages / 7.2.1: |
Ogden's Lemma for Regular Term Languages / 7.2.2: |
Constant Growth / 7.3: |
Constant Growth and Semilinearity / 7.3.1: |
Regular Term Languages are Semilinear / 7.3.2: |
Generative Capacity and Parsing Complexity / 7.3.3: |
Projection of String Languages / 8.1: |
Labelled Dependency Structures / 8.1.1: |
String-Generating Regular Dependency Grammars / 8.1.2: |
String-Generative Capacity / 8.1.3: |
String Languages and Structural Properties / 8.2: |
Masked Strings / 8.2.1: |
Enforcing a Given Block-Degree / 8.2.2: |
Enforcing Ill-Nestedness / 8.2.3: |
Hierarchies of String Languages / 8.2.4: |
Parsing Complexity / 8.2.5: |
Membership Problems / 8.3.1: |
The Standard Membership Problem / 8.3.2: |
The Uniform Membership Problem / 8.3.3: |
Recognition of Well-Nested Languages / 8.3.4: |
Conclusion / 8.3.5: |
Main Contributions / 9.1: |
Future Directions / 9.2: |
Development of the Formalism / 9.2.1: |
Linguistic Relevance / 9.2.2: |
Applications to Parsing / 9.2.3: |
An Algebraic Perspective on Grammar Formalisms / 9.2.4: |
References |
Index |
Introduction / 1: |
Motivation / 1.1: |
Dependency Structures / 1.1.1: |