Table of Contents

1. Cover
2. Introduction
3. 1 Programming with Graphs
   1. 1.1. Creating a graph
   2. 1.2. Feature structures
   3. 1.3. Information searches
   4. 1.4. Recreating an order
   5. 1.5. Using patterns with the GREW library
   6. 1.6. Graph rewriting
4. 2 Dependency Syntax: Surface Structure and Deep Structure
   1. 2.1. Dependencies versus constituents
   2. 2.2. Surface syntax: different types of syntactic dependency
   3. 2.3. Deep syntax
5. 3 Graph Rewriting and Transformation of Syntactic Annotations in a Corpus
   1. 3.1. Pattern matching in syntactically annotated corpora
   2. 3.2. From surface syntax to deep syntax
   3. 3.3. Conversion between surface syntax formats
6. 4 From Logic to Graphs for Semantic Representation
   1. 4.1. First order logic
   2. 4.2. Abstract meaning representation (AMR)
   3. 4.3. Minimal recursion semantics, MRS
7. 5 Application of Graph Rewriting to Semantic Annotation in a Corpus
   1. 5.1. Main stages in the transformation process
   2. 5.2. Limitations of the current system
   3. 5.3. Lessons in good practice
   4. 5.4. The DSQ_to_DMRS conversion system
8. 6 Parsing Using Graph Rewriting
   1. 6.1. The Cocke–Kasami–Younger parsing strategy
   2. 6.2. Reducing syntactic ambiguity
   3. 6.3. Description of the POS_to_SSQ rule system
   4. 6.4. Evaluation of the parser
9. 7 Graphs, Patterns and Rewriting
   1. 7.1. Graphs
   2. 7.2. Graph morphism
   3. 7.3. Patterns
   4. 7.4. Graph transformations
   5. 7.5. Graph rewriting system
   6. 7.6. Strategies
10. 8 Analysis of Graph Rewriting
    1. 8.1. Variations in rewriting
    2. 8.2. What can and cannot be computed
    3. 8.3. The problem of termination
    4. 8.4. Confluence and verification of confluence
11. Appendix
    1. A1.1. Sets
    2. A1.2. Relations and functions
    3. A1.3. Equivalences and orders
    4. A1.4. Languages and finite sequences
12. Bibliography
13. Index
14. End User License Agreement

List of Tables

1. 2 Dependency Syntax: Surface Structure and Deep Structure
   1. Table 2.1. Main syntactic dependency labels used in the SEQUOIA format
   2. Table 2.2. Main syntactic dependency labels used in the UD format

List of Illustrations

1. Introduction
   1. Figure I.1. Formats and rewriting systems considered in this book
2. 2 Dependency Syntax: Surface Structure and Deep Structure
   1. Figure 2.1. Constituent tree of sentence (2.1)
   2. Figure 2.2. Dependency tree for sentence (2.1)
3. 4 From Logic to Graphs for Semantic Representation
   1. Figure 4.1. An example of AMR represented as a graph
   2. Figure 4.2. A first graphical representation of RMRS modeling the semantics of the sentence “tous les enfants adorent un beau livre”
   3. Figure 4.3. RMRS for the sentence “tous les enfants adorent un beau livre” in graph form
   4. Figure 4.4. DMRSS of the sentence “tous les enfants adorent un beau livre”

Guide

1. Cover
2. Table of Contents
3. Begin Reading