Application of Graph Rewriting to Natural Language Processing

Guillaume Bonfante is a senior lecturer at the University of Lorraine, France.Bruno Guillaume is a researcher at Inria Nancy Grand-Est, France.Guy Perrier is Professor Emeritus at the University of Lorraine, France.

• Introduction ixChapter 1. Programming with Graphs 11.1. Creating a graph 21.2. Feature structures 51.3. Information searches 61.3.1. Access to nodes 71.3.2. Extracting edges 71.4. Recreating an order 91.5. Using patterns with the GREW library 111.5.1. Pattern syntax 131.5.2. Common pitfalls 161.6. Graph rewriting 201.6.1. Commands 221.6.2. From rules to strategies 241.6.3. Using lexicons 291.6.4. Packages 311.6.5. Common pitfalls 32Chapter 2. Dependency Syntax: Surface Structure and Deep Structure 352.1. Dependencies versus constituents 362.2. Surface syntax: different types of syntactic dependency 422.2.1. Lexical word arguments 442.2.2. Modifiers 492.2.3. Multiword expressions 512.2.4. Coordination 532.2.5. Direction of dependencies between functional and lexical words 552.3. Deep syntax 582.3.1. Example 592.3.2. Subjects of infinitives, participles, coordinated verbs and adjectives 612.3.3. Neutralization of diatheses 612.3.4. Abstraction of focus and topicalization procedures 642.3.5. Deletion of functional words 662.3.6. Coordination in deep syntax 68Chapter 3. Graph Rewriting and Transformation of Syntactic Annotations in a Corpus 713.1. Pattern matching in syntactically annotated corpora 723.1.1. Corpus correction 723.1.2. Searching for linguistic examples in a corpus 773.2. From surface syntax to deep syntax 793.2.1. Main steps in the SSQ_to_DSQ transformation 803.2.2. Lessons in good practice 833.2.3. The UD_to_AUD transformation system 903.2.4. Evaluation of the SSQ_to_DSQ and UD_to_AUD systems 913.3. Conversion between surface syntax formats 923.3.1. Differences between the SSQ and UD annotation schemes 923.3.2. The SSQ to UD format conversion system 983.3.3. The UD to SSQ format conversion system 100Chapter 4. From Logic to Graphs for Semantic Representation 1034.1. First order logic 1044.1.1. Propositional logic 1044.1.2. Formula syntax in FOL 1064.1.3. Formula semantics in FOL 1074.2. Abstract meaning representation (AMR) 1084.2.1. General overview of AMR 1094.2.2. Examples of phenomena modeled using AMR 1134.3. Minimal recursion semantics, MRS 1184.3.1. Relations between quantifier scopes 1184.3.2. Why use an underspecified semantic representation? 1204.3.3. The RMRS formalism 1224.3.4. Examples of phenomenon modeling in MRS 1334.3.5. From RMRS to DMRS 137Chapter 5. Application of Graph Rewriting to Semantic Annotation in a Corpus 1435.1. Main stages in the transformation process 1445.1.1. Uniformization of deep syntax 1445.1.2. Determination of nodes in the semantic graph 1455.1.3. Central arguments of predicates 1475.1.4. Non-core arguments of predicates 1475.1.5. Final cleaning 1485.2. Limitations of the current system 1495.3. Lessons in good practice 1505.3.1. Decomposing packages 1505.3.2. Ordering packages 1515.4. The DSQ_to_DMRS conversion system 1545.4.1. Modifiers 1545.4.2. Determiners 156Chapter 6. Parsing Using Graph Rewriting 1596.1. The Cocke–Kasami–Younger parsing strategy 1606.1.1. Introductory example 1606.1.2. The parsing algorithm 1636.1.3. Start with non-ambiguous compositions 1646.1.4. Revising provisional choices once all information is available 1656.2. Reducing syntactic ambiguity 1696.2.1. Determining the subject of a verb 1706.2.2. Attaching complements found on the right of their governors 1726.2.3. Attaching other complements 1766.2.4. Realizing interrogatives and conjunctive and relative subordinates 1796.3. Description of the POS_to_SSQ rule system 1806.4. Evaluation of the parser 185Chapter 7. Graphs, Patterns and Rewriting 1877.1. Graphs 1897.2. Graph morphism 1927.3. Patterns 1957.3.1. Pattern decomposition in a graph 1987.4. Graph transformations 1987.4.1. Operations on graphs 1997.4.2. Command language 2007.5. Graph rewriting system 2027.5.1. Semantics of rewriting 2057.5.2. Rule uniformity 2067.6. Strategies 206Chapter 8. Analysis of Graph Rewriting 2098.1. Variations in rewriting 2128.1.1. Label changes 2138.1.2. Addition and deletion of edges 2148.1.3. Node deletion 2158.1.4. Global edge shifts 2158.2. What can and cannot be computed 2178.3. The problem of termination 2208.3.1. Node and edge weights 2218.3.2. Proof of the termination theorem 2248.4. Confluence and verification of confluence 229Appendix 237Bibliography 241Index 247