Dependency Structures and Lexicalized Grammars

An Algebraic Approach

By: Marco Kuhlmann (Editor)

Write A Review

Paperback | 30 July 2010

At a Glance

Paperback
152 Pages

Dimensions(cm)
24.13 x 15.88 x 1.27

Paperback

$84.99

or 4 interest-free payments of $21.25 with

Ships in 5 to 7 business days

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.

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

Orders over $79.00 qualify for free shipping.

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

You Can Find This Book In

Non-Fiction Language & Linguistics Linguistics Computing & I.T.Computer Science Computer Architecture & Logic Design Mathematics Mathematical Foundation Mathematical Logic Artificial Intelligence Natural Language & Machine Translation

Introduction	p. 1
Motivation	p. 1
Dependency Structures	p. 1
Generative Capacity and Non-projectivity	p. 3
Lexicalized Grammars Induce Dependency Trees	p. 4
Overview of the Book	p. 7
Dependency Structures	p. 7
Dependency Languages	p. 9
Contributions	p. 10
Preliminaries	p. 11
Projective Dependency Structures	p. 17
Projectivity	p. 17
Projectivity in the Sense of Harper and Hays	p. 18
Projectivity in the Sense of Lecerf and Ihm	p. 19
Projectivity in the Sense of Fitialov	p. 19
Related Work	p. 20
Algebraic Framework	p. 20
Tree Traversal Strategies	p. 21
Traversal of Treelet-Ordered Trees	p. 23
Order Annotations	p. 26
Dependency Algebras	p. 26
Algorithmic Problems	p. 28
Encoding and Decoding	p. 28
Testing whether a Dependency Structure Is Projective	p. 29
Related Work	p. 29
Empirical Evaluation	p. 30
The Projectivity Hypothesis	p. 30
Experimental Setup	p. 31
Results and Discussion	p. 31
Related Work	p. 32
Dependency Structures of Bounded Degree	p. 33
The Block-Degree Measure	p. 33
Blocks and Block-Degree	p. 33
A Hierarchy of Non-projective Dependency Structures	p. 35
Related Work	p. 36
Algebraic Framework	p. 37
Traversal of Block-Ordered Trees	p. 38
Segmented Dependency Structures	p. 40
Order Annotations	p. 42
Dependency Structure Algebras	p. 43
Algorithmic Problems	p. 44
Encoding	p. 44
Computing the Block-Degree of a Dependency Structure	p. 48
Empirical Evaluation	p. 48
Dependency Structures without Crossings	p. 51
Weakly Non-projective Dependency Structures	p. 51
Definition of Weak Non-projectivity	p. 52
Relation to the Block-Degree Measure	p. 53
Algebraic Opaqueness	p. 54
Related Work	p. 54
Well-Nested Dependency Structures	p. 56
Definition of Well-Nestedness	p. 56
Non-crossing Partitions	p. 57
Algebraic Characterization	p. 59
Testing whether a Dependency Structure Is Well-Nested	p. 60
Related Work	p. 60
Empirical Evaluation	p. 61
Structures and Grammars	p. 63
Context-Free Grammars	p. 63
Definition	p. 64
String Semantics	p. 65
Linearization Semantics	p. 66
Dependency Semantics	p. 67
Linear Context-Free Rewriting Systems	p. 68
Definition	p. 69
String Semantics	p. 70
Non-essential Concatenation Functions	p. 71
Linearization Semantics	p. 73
Dependency Semantics	p. 74
Related Work	p. 75
Coupled Context-Free Grammars	p. 75
Definition	p. 75
String Semantics	p. 77
Dependency Semantics	p. 78
Related Work	p. 79
Tree Adjoining Grammar	p. 79
Definition	p. 80
Linearization Semantics	p. 81
Related Work	p. 82
Regular Dependency Languages	p. 85
Regular Sets of Dependency Structures	p. 85
Algebraic Recognizability	p. 86
Elementary Properties	p. 87
Regular Term Grammars	p. 89
Regular Dependency Grammars	p. 90
Dependency Languages and Lexicalized Grammars	p. 92
Pumping Lemmata	p. 93
The Pumping Lemma for Regular Term Languages	p. 93
Ogden's Lemma for Regular Term Languages	p. 95
Constant Growth	p. 97
Constant Growth and Semilinearity	p. 98
Regular Term Languages are Semilinear	p. 100
Related Work	p. 102
Generative Capacity and Parsing Complexity	p. 103
Projection of String Languages	p. 103
Labelled Dependency Structures	p. 103
String-Generating Regular Dependency Grammars	p. 105
String-Generative Capacity	p. 105
String Languages and Structural Properties	p. 107
Masked Strings	p. 107
Enforcing a Given Block-Degree	p. 108
Enforcing Ill-Nestedness	p. 110
Hierarchies of String Languages	p. 112
Related Work	p. 113
Parsing Complexity	p. 113
Membership Problems	p. 113
The Standard Membership Problem	p. 115
The Uniform Membership Problem	p. 116
Recognition of Well-Nested Languages	p. 119
Related Work	p. 120
Conclusion	p. 121
Main Contributions	p. 121
Future Directions	p. 121
Development of the Formalism	p. 123
Linguistic Relevance	p. 123
Applications to Parsing	p. 124
An Algebraic Perspective on Grammar Formalisms	p. 124
References	p. 127
Index	p. 135
Table of Contents provided by Ingram. All Rights Reserved.

Dependency Structures and Lexicalized Grammars

An Algebraic Approach

At a Glance

Paperback

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Computer Science

The Tech Coup

How to Save Democracy from Silicon Valley

Python Crash Course

3rd Edition - A Hands-On, Project-Based Introduction to Programming

Nexus

A Brief History of Information Networks from the Stone Age to AI

Microsoft 365 Excel For Dummies

For Dummies (Computer/Tech)

New Beginnings

why change is so difficult and how to achieve it

If Anyone Builds It, Everyone Dies

The Case Against Superintelligent AI

The New Age of Sexism

How the AI Revolution is Reinventing Misogyny

The AI Con

How To Fight Big Tech's Hype and Create the Future We Want

Microsoft 365 Excel All-in-One For Dummies

Excel for Dummies

Creative Machines

AI, Art & Us

Genesis

Artificial Intelligence, Hope, and the Human Spirit

The AI-Driven Leader

Harnessing AI to Make Faster, Smarter Decisions

Empire of AI

Inside the reckless race for total domination

Python All-in-One For Dummies

3rd Edition

Hands-On Machine Learning with Scikit-Learn and PyTorch

Concepts, Tools, and Techniques to Build Intelligent Systems

Life 3.0

Being Human in the Age of Artificial Intelligence

Data Science and Machine Learning for Non-Programmers

Using SAS Enterprise Miner

Explainable Artificial Intelligence-based Industrial Internet of Things

Technologies and Applications

Autonomous Cyber Resilience

Causal Inference and Machine Learning

In Economics, Social, and Health Sciences

Unleashing User Innovation

Multidisciplinary Perspectives on End-User Development and Generative AI

The Shortest History of AI

Co-Intelligence

Living and Working with AI

Scary Smart

The Future of Artificial Intelligence and How You Can Save Our World

This product is categorised by