Details

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

<strong>Guy Perrier</strong>, Emeritus Professor at Université de Lorraine (France). <p><strong>Bruno Guillaume</strong>, Researcher at INRIA. <p><strong>Guillaume Bonfante</strong>, Associate Professor at Université de Lorraine.

US