Amazon cover image
Image from Amazon.com

Parsing Schemata for Practical Text Analysis.

By: Series: Mathematics, Computing, Language, and Life: Frontiers in Mathematical Linguistics and Language Theory SerPublisher: Singapore : Imperial College Press, 2010Copyright date: ©2010Description: 1 online resource (290 pages)Content type:
  • text
Media type:
  • computer
Carrier type:
  • online resource
ISBN:
  • 9781848165618
Subject(s): Genre/Form: Additional physical formats: Print version:: Parsing Schemata for Practical Text AnalysisDDC classification:
  • 005.45
LOC classification:
  • P98 -- .G66 2010eb
Online resources:
Contents:
Intro -- Contents -- Preface -- List of Figures -- Introduction and Preliminaries -- 1. Introduction -- 1.1 Motivation -- 1.2 Background -- 1.2.1 Parsing natural language -- 1.2.2 Robustness in grammar-driven parsers -- 1.2.3 Parsing schemata -- 1.3 Outline of the book -- 1.3.1 Contributions -- 1.3.2 Structure of the book -- 1.3.2.1 Part 1 -- 1.3.2.2 Part 2 -- 1.3.2.3 Part 3 -- 1.3.2.4 Part 4 -- 1.3.2.5 Part 5 -- 2. Preliminaries -- 2.1 Context-free grammars -- 2.2 Parsing algorithms and schemata -- 2.3 The formalism of parsing schemata -- 2.3.1 Deduction systems -- 2.3.2 Parsing systems and parsing schemata -- 2.3.3 Correctness of parsing schemata -- 2.3.4 Relations between parsing schemata -- 2.4 Advantages of parsing schemata -- Compiling and Executing Parsing Schemata -- 3. A compiler for parsing schemata -- 3.1 Motivation and goals -- 3.1.1 Design goals -- 3.1.2 Related work -- 3.2 System architecture -- 3.3 Generated code -- 3.4 Reading schemata -- 3.5 The code generation process -- 3.5.1 Element types -- 3.5.2 Deduction step classes -- 3.5.3 Deduction step code generation -- 3.5.4 Search specifications -- 3.6 Indexing -- 3.6.1 Static analysis and index descriptors -- 3.6.2 Generation of indexing code -- 3.6.3 Deduction step indexing -- 3.7 Discussion -- 4. Practical complexity of constituency parsers -- 4.1 Parsing natural language with CFGs -- 4.2 Parsing with TAGs -- 4.2.1 Tree-adjoining grammars -- 4.2.2 Substitution and adjunction -- 4.2.3 Properties of TAG -- 4.3 Parsing schemata for TAG -- 4.4 Parsing schemata for the XTAG English grammar -- 4.4.1 Grammar conversion -- 4.4.2 Feature structure unification -- 4.4.3 Tree filtering -- 4.4.3.1 Example -- 4.5 Comparing several parsers for the XTAG grammar -- 4.6 Parsing with artificially-generated TAGs -- 4.7 Overhead of TAG parsing over CFG parsing -- 4.8 Discussion.
Parsing Schemata for Error-Repair Parsers -- 5. Error-repair parsing schemata -- 5.1 Motivation -- 5.2 Error repair in parsing schemata -- 5.2.1 The formalism of error-repair parsing schemata -- 5.2.2 A tree distance for edit distance-based repair -- 5.3 Lyon's error-repair parser -- 5.3.1 Lyon is correct -- 5.3.1.1 Soundness -- 5.3.1.2 Completeness -- 5.4 Obtaining minimal distance parses -- 5.5 Global and regional error repair -- 5.5.1 Performance of global and regional parsers -- 5.6 Discussion -- 6. Transforming standard parsers into error-repair parsers -- 6.1 From standard parsers to error-repair parsers -- 6.1.1 Outline of the transformation -- 6.2 Formal description of the error-repair transformation -- 6.2.1 Some properties of trees and items -- 6.2.2 Some properties of deduction steps -- 6.2.3 The error-repair transformation -- 6.2.3.1 Items of the error-repair transformation -- 6.2.3.2 Deduction steps of the error-repair transformation -- 6.3 Proof of correctness of the error-repair transformation -- 6.3.1 Proof of Theorem 6.1 -- 6.3.1.1 Proof for case (1) -- 6.3.1.2 Proof for case (2) -- 6.3.1.3 Proof for fixed deduction step sets -- 6.3.2 Proof of Theorem 6.2 -- 6.3.2.1 Base case (e=0) -- 6.3.2.2 Induction step -- 6.3.2.3 End of the proof of Theorem 6.2 -- 6.4 Optimising the results of the transformation -- 6.5 Discussion -- Parsing Schemata for Dependency Parsers -- 7. Dependency parsing schemata -- 7.1 Motivation -- 7.2 The formalism of dependency parsing schemata -- 7.3 Parsing schemata for projective dependency parsers -- 7.3.1 Collins (1996) -- 7.3.2 Eisner (1996) -- 7.3.3 Eisner and Satta (1999) -- 7.3.4 Yamada and Matsumoto (2003) -- 7.3.5 Lombardo and Lesmo (1996) and other Earleybased parsers -- 7.3.6 Nivre (2003) -- 7.3.7 Covington's projective parser (Covington, 2001) -- 7.4 Relations between dependency parsers.
7.4.1 Yamada and Matsumoto (2003) → Eisner (1996) -- 7.4.2 Eisner and Satta (1999) → Eisner (1996) -- 7.4.3 Other relations -- 7.5 Proving the correctness of dependency parsers -- 7.5.1 Eisner and Satta (1999) is correct -- 7.5.2 Yamada and Matsumoto (2003) is correct -- 7.5.3 Eisner (1996) is correct -- 7.6 Parsing schemata for non-projective dependency parsers -- 7.6.1 Pseudo-projectivity -- 7.6.2 Attardi (2006) and the MHk parser -- 7.6.3 MST parser (McDonald et al., 2005b) -- 7.6.4 Covington's non-projective parser (Covington, 1990 -- 2001) -- 7.7 Parsing schemata for Link Grammar parsers -- 7.7.1 Sleator and Temperley's LG parser -- 7.7.2 Adapting projective dependency parsers to LG -- 7.7.3 Eisner (1996) for LG -- 7.7.4 Eisner and Satta (1999) for LG -- 7.7.5 Yamada and Matsumoto (2003) for LG -- 7.8 Discussion -- 8. Mildly non-projective dependency parsing -- 8.1 Motivation -- 8.2 Preliminaries -- 8.3 The WG1 parser -- 8.3.1 WG1 parsing schema -- 8.3.2 Proof of correctness for WG -- 8.3.2.1 Soundness -- 8.3.2.2 Order annotations -- 8.3.2.3 Completeness -- 8.3.2.4 Proof of Lemma 8.1 -- 8.3.3 Computational complexity of WG1 -- 8.4 The WGk parser -- 8.4.1 WGk parsing schema -- 8.4.2 Proof of correctness for WGk -- 8.4.3 Computational complexity of WGk -- 8.5 Parsing ill-nested structures -- 8.5.1 The MG1 and MGk parsers -- 8.5.2 Complexity of MGk -- 8.5.3 Proof of correctness for MGk -- 8.5.3.1 Soundness -- 8.5.3.2 Completeness -- 8.5.3.3 Proof of Lemma 8.2 -- 8.5.4 Mildly ill-nested dependency structures -- 8.6 Discussion -- Conclusion -- 9. Conclusions -- 9.1 Future work -- List of Acronyms -- Bibliography -- Index.
Summary: The book presents a wide range of recent research results about parsing schemata, introducing formal frameworks and theoretical results while keeping a constant focus on applicability to practical parsing problems. The first part includes a general introduction to the parsing schemata formalism that contains the basic notions needed to understand the rest of the parts. Thus, this compendium can be used as an introduction to natural language parsing, allowing postgraduate students not only to get a solid grasp of the fundamental concepts underlying parsing algorithms, but also an understanding of the latest developments and challenges in the field. Researchers in computational linguistics will find novel results where parsing schemata are applied to current problems that are being actively researched in the computational linguistics community (like dependency parsing, robust parsing, or the treatment of non-projective linguistics phenomena). This book not only explains these results in a more detailed, comprehensive and self-contained way, and highlights the relations between them, but also includes new contributions that have not been presented.
Holdings
Item type Current library Call number Status Date due Barcode Item holds
Ebrary Ebrary Afghanistan Available EBKAF00053259
Ebrary Ebrary Algeria Available
Ebrary Ebrary Cyprus Available
Ebrary Ebrary Egypt Available
Ebrary Ebrary Libya Available
Ebrary Ebrary Morocco Available
Ebrary Ebrary Nepal Available EBKNP00053259
Ebrary Ebrary Sudan Available
Ebrary Ebrary Tunisia Available
Total holds: 0

Intro -- Contents -- Preface -- List of Figures -- Introduction and Preliminaries -- 1. Introduction -- 1.1 Motivation -- 1.2 Background -- 1.2.1 Parsing natural language -- 1.2.2 Robustness in grammar-driven parsers -- 1.2.3 Parsing schemata -- 1.3 Outline of the book -- 1.3.1 Contributions -- 1.3.2 Structure of the book -- 1.3.2.1 Part 1 -- 1.3.2.2 Part 2 -- 1.3.2.3 Part 3 -- 1.3.2.4 Part 4 -- 1.3.2.5 Part 5 -- 2. Preliminaries -- 2.1 Context-free grammars -- 2.2 Parsing algorithms and schemata -- 2.3 The formalism of parsing schemata -- 2.3.1 Deduction systems -- 2.3.2 Parsing systems and parsing schemata -- 2.3.3 Correctness of parsing schemata -- 2.3.4 Relations between parsing schemata -- 2.4 Advantages of parsing schemata -- Compiling and Executing Parsing Schemata -- 3. A compiler for parsing schemata -- 3.1 Motivation and goals -- 3.1.1 Design goals -- 3.1.2 Related work -- 3.2 System architecture -- 3.3 Generated code -- 3.4 Reading schemata -- 3.5 The code generation process -- 3.5.1 Element types -- 3.5.2 Deduction step classes -- 3.5.3 Deduction step code generation -- 3.5.4 Search specifications -- 3.6 Indexing -- 3.6.1 Static analysis and index descriptors -- 3.6.2 Generation of indexing code -- 3.6.3 Deduction step indexing -- 3.7 Discussion -- 4. Practical complexity of constituency parsers -- 4.1 Parsing natural language with CFGs -- 4.2 Parsing with TAGs -- 4.2.1 Tree-adjoining grammars -- 4.2.2 Substitution and adjunction -- 4.2.3 Properties of TAG -- 4.3 Parsing schemata for TAG -- 4.4 Parsing schemata for the XTAG English grammar -- 4.4.1 Grammar conversion -- 4.4.2 Feature structure unification -- 4.4.3 Tree filtering -- 4.4.3.1 Example -- 4.5 Comparing several parsers for the XTAG grammar -- 4.6 Parsing with artificially-generated TAGs -- 4.7 Overhead of TAG parsing over CFG parsing -- 4.8 Discussion.

Parsing Schemata for Error-Repair Parsers -- 5. Error-repair parsing schemata -- 5.1 Motivation -- 5.2 Error repair in parsing schemata -- 5.2.1 The formalism of error-repair parsing schemata -- 5.2.2 A tree distance for edit distance-based repair -- 5.3 Lyon's error-repair parser -- 5.3.1 Lyon is correct -- 5.3.1.1 Soundness -- 5.3.1.2 Completeness -- 5.4 Obtaining minimal distance parses -- 5.5 Global and regional error repair -- 5.5.1 Performance of global and regional parsers -- 5.6 Discussion -- 6. Transforming standard parsers into error-repair parsers -- 6.1 From standard parsers to error-repair parsers -- 6.1.1 Outline of the transformation -- 6.2 Formal description of the error-repair transformation -- 6.2.1 Some properties of trees and items -- 6.2.2 Some properties of deduction steps -- 6.2.3 The error-repair transformation -- 6.2.3.1 Items of the error-repair transformation -- 6.2.3.2 Deduction steps of the error-repair transformation -- 6.3 Proof of correctness of the error-repair transformation -- 6.3.1 Proof of Theorem 6.1 -- 6.3.1.1 Proof for case (1) -- 6.3.1.2 Proof for case (2) -- 6.3.1.3 Proof for fixed deduction step sets -- 6.3.2 Proof of Theorem 6.2 -- 6.3.2.1 Base case (e=0) -- 6.3.2.2 Induction step -- 6.3.2.3 End of the proof of Theorem 6.2 -- 6.4 Optimising the results of the transformation -- 6.5 Discussion -- Parsing Schemata for Dependency Parsers -- 7. Dependency parsing schemata -- 7.1 Motivation -- 7.2 The formalism of dependency parsing schemata -- 7.3 Parsing schemata for projective dependency parsers -- 7.3.1 Collins (1996) -- 7.3.2 Eisner (1996) -- 7.3.3 Eisner and Satta (1999) -- 7.3.4 Yamada and Matsumoto (2003) -- 7.3.5 Lombardo and Lesmo (1996) and other Earleybased parsers -- 7.3.6 Nivre (2003) -- 7.3.7 Covington's projective parser (Covington, 2001) -- 7.4 Relations between dependency parsers.

7.4.1 Yamada and Matsumoto (2003) → Eisner (1996) -- 7.4.2 Eisner and Satta (1999) → Eisner (1996) -- 7.4.3 Other relations -- 7.5 Proving the correctness of dependency parsers -- 7.5.1 Eisner and Satta (1999) is correct -- 7.5.2 Yamada and Matsumoto (2003) is correct -- 7.5.3 Eisner (1996) is correct -- 7.6 Parsing schemata for non-projective dependency parsers -- 7.6.1 Pseudo-projectivity -- 7.6.2 Attardi (2006) and the MHk parser -- 7.6.3 MST parser (McDonald et al., 2005b) -- 7.6.4 Covington's non-projective parser (Covington, 1990 -- 2001) -- 7.7 Parsing schemata for Link Grammar parsers -- 7.7.1 Sleator and Temperley's LG parser -- 7.7.2 Adapting projective dependency parsers to LG -- 7.7.3 Eisner (1996) for LG -- 7.7.4 Eisner and Satta (1999) for LG -- 7.7.5 Yamada and Matsumoto (2003) for LG -- 7.8 Discussion -- 8. Mildly non-projective dependency parsing -- 8.1 Motivation -- 8.2 Preliminaries -- 8.3 The WG1 parser -- 8.3.1 WG1 parsing schema -- 8.3.2 Proof of correctness for WG -- 8.3.2.1 Soundness -- 8.3.2.2 Order annotations -- 8.3.2.3 Completeness -- 8.3.2.4 Proof of Lemma 8.1 -- 8.3.3 Computational complexity of WG1 -- 8.4 The WGk parser -- 8.4.1 WGk parsing schema -- 8.4.2 Proof of correctness for WGk -- 8.4.3 Computational complexity of WGk -- 8.5 Parsing ill-nested structures -- 8.5.1 The MG1 and MGk parsers -- 8.5.2 Complexity of MGk -- 8.5.3 Proof of correctness for MGk -- 8.5.3.1 Soundness -- 8.5.3.2 Completeness -- 8.5.3.3 Proof of Lemma 8.2 -- 8.5.4 Mildly ill-nested dependency structures -- 8.6 Discussion -- Conclusion -- 9. Conclusions -- 9.1 Future work -- List of Acronyms -- Bibliography -- Index.

The book presents a wide range of recent research results about parsing schemata, introducing formal frameworks and theoretical results while keeping a constant focus on applicability to practical parsing problems. The first part includes a general introduction to the parsing schemata formalism that contains the basic notions needed to understand the rest of the parts. Thus, this compendium can be used as an introduction to natural language parsing, allowing postgraduate students not only to get a solid grasp of the fundamental concepts underlying parsing algorithms, but also an understanding of the latest developments and challenges in the field. Researchers in computational linguistics will find novel results where parsing schemata are applied to current problems that are being actively researched in the computational linguistics community (like dependency parsing, robust parsing, or the treatment of non-projective linguistics phenomena). This book not only explains these results in a more detailed, comprehensive and self-contained way, and highlights the relations between them, but also includes new contributions that have not been presented.

Description based on publisher supplied metadata and other sources.

Electronic reproduction. Ann Arbor, Michigan : ProQuest Ebook Central, 2019. Available via World Wide Web. Access may be limited to ProQuest Ebook Central affiliated libraries.

There are no comments on this title.

to post a comment.