Application of Graph Rewriting to Natural Language Processing

The paradigm of Graph Rewriting is used very little in the field of Natural Language Processing. But graphs are a natural way of representing the deep syntax and the semantics of natural languages. Deep syntax is an abstraction of syntactic dependencies towards semantics in the form of graphs and there is a compact way of representing the semantics in an underspecified logical framework also with graphs. Then, Graph Rewriting reconciles efficiency with linguistic readability for producing representations at some linguistic level by transformation of a neighbor level: from raw text to surface syntax, from surface syntax to deep syntax, from deep syntax to underspecified logical semantics and conversely.

Table of Contents:
Introduction ix Chapter 1. Programming with Graphs 1 1.1. Creating a graph 2 1.2. Feature structures 5 1.3. Information searches 6 1.3.1. Access to nodes 7 1.3.2. Extracting edges 7 1.4. Recreating an order 9 1.5. Using patterns with the GREW library 11 1.5.1. Pattern syntax 13 1.5.2. Common pitfalls 16 1.6. Graph rewriting 20 1.6.1. Commands 22 1.6.2. From rules to strategies 24 1.6.3. Using lexicons 29 1.6.4. Packages 31 1.6.5. Common pitfalls 32 Chapter 2. Dependency Syntax: Surface Structure and Deep Structure 35 2.1. Dependencies versus constituents 36 2.2. Surface syntax: different types of syntactic dependency 42 2.2.1. Lexical word arguments 44 2.2.2. Modifiers 49 2.2.3. Multiword expressions 51 2.2.4. Coordination 53 2.2.5. Direction of dependencies between functional and lexical words 55 2.3. Deep syntax 58 2.3.1. Example 59 2.3.2. Subjects of infinitives, participles, coordinated verbs and adjectives 61 2.3.3. Neutralization of diatheses 61 2.3.4. Abstraction of focus and topicalization procedures 64 2.3.5. Deletion of functional words 66 2.3.6. Coordination in deep syntax 68 Chapter 3. Graph Rewriting and Transformation of Syntactic Annotations in a Corpus 71 3.1. Pattern matching in syntactically annotated corpora 72 3.1.1. Corpus correction 72 3.1.2. Searching for linguistic examples in a corpus 77 3.2. From surface syntax to deep syntax 79 3.2.1. Main steps in the SSQ_to_DSQ transformation 80 3.2.2. Lessons in good practice 83 3.2.3. The UD_to_AUD transformation system 90 3.2.4. Evaluation of the SSQ_to_DSQ and UD_to_AUD systems 91 3.3. Conversion between surface syntax formats 92 3.3.1. Differences between the SSQ and UD annotation schemes 92 3.3.2. The SSQ to UD format conversion system 98 3.3.3. The UD to SSQ format conversion system 100 Chapter 4. From Logic to Graphs for Semantic Representation 103 4.1. First order logic 104 4.1.1. Propositional logic 104 4.1.2. Formula syntax in FOL 106 4.1.3. Formula semantics in FOL 107 4.2. Abstract meaning representation (AMR) 108 4.2.1. General overview of AMR 109 4.2.2. Examples of phenomena modeled using AMR 113 4.3. Minimal recursion semantics, MRS 118 4.3.1. Relations between quantifier scopes 118 4.3.2. Why use an underspecified semantic representation? 120 4.3.3. The RMRS formalism 122 4.3.4. Examples of phenomenon modeling in MRS 133 4.3.5. From RMRS to DMRS 137 Chapter 5. Application of Graph Rewriting to Semantic Annotation in a Corpus 143 5.1. Main stages in the transformation process 144 5.1.1. Uniformization of deep syntax 144 5.1.2. Determination of nodes in the semantic graph 145 5.1.3. Central arguments of predicates 147 5.1.4. Non-core arguments of predicates 147 5.1.5. Final cleaning 148 5.2. Limitations of the current system 149 5.3. Lessons in good practice 150 5.3.1. Decomposing packages 150 5.3.2. Ordering packages 151 5.4. The DSQ_to_DMRS conversion system 154 5.4.1. Modifiers 154 5.4.2. Determiners 156 Chapter 6. Parsing Using Graph Rewriting 159 6.1. The Cocke–Kasami–Younger parsing strategy 160 6.1.1. Introductory example 160 6.1.2. The parsing algorithm 163 6.1.3. Start with non-ambiguous compositions 164 6.1.4. Revising provisional choices once all information is available 165 6.2. Reducing syntactic ambiguity 169 6.2.1. Determining the subject of a verb 170 6.2.2. Attaching complements found on the right of their governors 172 6.2.3. Attaching other complements 176 6.2.4. Realizing interrogatives and conjunctive and relative subordinates 179 6.3. Description of the POS_to_SSQ rule system 180 6.4. Evaluation of the parser 185 Chapter 7. Graphs, Patterns and Rewriting 187 7.1. Graphs 189 7.2. Graph morphism 192 7.3. Patterns 195 7.3.1. Pattern decomposition in a graph 198 7.4. Graph transformations 198 7.4.1. Operations on graphs 199 7.4.2. Command language 200 7.5. Graph rewriting system 202 7.5.1. Semantics of rewriting 205 7.5.2. Rule uniformity 206 7.6. Strategies 206 Chapter 8. Analysis of Graph Rewriting 209 8.1. Variations in rewriting 212 8.1.1. Label changes 213 8.1.2. Addition and deletion of edges 214 8.1.3. Node deletion 215 8.1.4. Global edge shifts 215 8.2. What can and cannot be computed 217 8.3. The problem of termination 220 8.3.1. Node and edge weights 221 8.3.2. Proof of the termination theorem 224 8.4. Confluence and verification of confluence 229 Appendix 237 Bibliography 241 Index 247

About the Author :
Guy Perrier, Emeritus Professor at Université de Lorraine (France). Bruno Guillaume, Researcher at INRIA. Guillaume Bonfante, Associate Professor at Université de Lorraine.