acl acl2010 acl2010-182 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Sylvain Schmitz
Abstract: Dominance links were introduced in grammars to model long distance scrambling phenomena, motivating the definition of multiset-valued linear indexed grammars (MLIGs) by Rambow (1994b), and inspiring quite a few recent formalisms. It turns out that MLIGs have since been rediscovered and reused in a variety of contexts, and that the complexity of their emptiness problem has become the key to several open questions in computer science. We survey complexity results and open issues on MLIGs and related formalisms, and provide new complexity bounds for some linguistically motivated restrictions.
Reference: text
sentIndex sentText sentNum sentScore
1 On the Computational Complexity of Dominance Links in Grammatical Formalisms Sylvain Schmitz LSV, ENS Cachan & CNRS, France sylvain . [sent-1, score-0.099]
2 s chmit z @ l sv Abstract Dominance links were introduced in grammars to model long distance scrambling phenomena, motivating the definition of multiset-valued linear indexed grammars (MLIGs) by Rambow (1994b), and inspiring quite a few recent formalisms. [sent-2, score-0.645]
3 It turns out that MLIGs have since been rediscovered and reused in a variety of contexts, and that the complexity of their emptiness problem has become the key to several open questions in computer science. [sent-3, score-0.706]
4 We survey complexity results and open issues on MLIGs and related formalisms, and provide new complexity bounds for some linguistically motivated restrictions. [sent-4, score-0.372]
5 , 1991 ; Rambow, 1994a; Lichte, 2007), cause notorious difficulties to linguistic modeling in classical grammar formalisms like HPSG or TAG. [sent-6, score-0.236]
6 Rambow (1994b) introduced a formalism, unordered vector grammars with dominance links (UVG-dls), for modeling such phenomena. [sent-8, score-0.548]
7 These grammars are defined by vectors of contextfree productions along with dominance links that . [sent-9, score-0.588]
8 fr NPnomVP NPacV PV repVa rPiert Figure 1: A vector of productions for the verb repariert together with its two complements. [sent-11, score-0.379]
9 should be enforced during derivations; for instance, Figure 1 shows how a flexible order between the complements of repariert could be expressed in an UVG-dl. [sent-12, score-0.426]
10 Similar dominance mechanisms have been employed in various tree description formalisms (Rambow et al. [sent-13, score-0.474]
11 It is a natural extension of Petri nets, with broader scope than just UVG-dls; indeed, it has been independently rediscovered by de Groote et al. [sent-18, score-0.143]
12 (2004) in the context of linear logic, and by Verma and Goubault-Larrecq (2005) in that ofequational theories. [sent-19, score-0.039]
13 Moreover, the decidability of its emptiness problem has proved to be quite challenging and is still uncertain, with several open questions depending on its resolution: • provability in multiplicative exponential linear logic (de nG mrouoltteip elitc al. [sent-20, score-0.548]
14 , 2004), • emptiness and membership of abstract categorial grammars (de Gshriopot oef e atb al. [sent-21, score-0.706]
15 , 2004; Yoshinaka and Kanazawa, 2005), • emptiness and membership of Stabler (1997)’s minimalist grammars without 514 Proce dinUgsp osfa tlhae, 4S8wthed Aen n,u 1a1l-1 M6e Jeutilnyg 2 o0f1 t0h. [sent-22, score-0.774]
16 c As2s0o1c0ia Atisosnoc foiart Cionom fopru Ctaotmiopnuatla Lti on gaulis Lti cnsg,u piasgtiecs 514–524, shortest move constraint (Salvati, 2010), satisfiability of first-order logic on data tsraeteissf (Boja ´nczyk e fit al. [sent-24, score-0.198]
17 , 2009), oangidc cof o course • emptiness and membership for the various feomrmptainliessmss tnhdat memembebde rUshViGp- fdolrs. [sent-25, score-0.579]
18 Unsurprisingly in the light of their importance in different fields, several authors have started investigating the complexity of decisions problems for MLIGs (Demri et al. [sent-26, score-0.099]
19 We survey the current state of affairs, with a particular emphasis on two points: 1. [sent-28, score-0.104]
20 the applicability of complexity results to UVG-dls, which is needed if we are to conclude anything on related formalisms with dominance links, 2. [sent-29, score-0.541]
21 the effects of two linguistically motivated restrictions on such formalisms, lexicalization and boundedness/rankedness. [sent-30, score-0.108]
22 This also implies an EXPTIME lower bound for emptiness and membership in minimalist grammars with shortest move constraint. [sent-32, score-0.866]
23 We first define MLIGs formally in Section 2 and review related formalisms in Section 3. [sent-33, score-0.194]
24 We proceed with complexity results in Section 4 before concluding in Section 5. [sent-34, score-0.134]
25 Notations In the following, Σ denotes a finite alphabet, Σ∗ the set of finite sentences over Σ, and ε the empty string. [sent-35, score-0.111]
26 The length of a string w is noted |w| , and the number of occurrence of a symbol a |inw w aisn dn othteed n |w|a. [sent-36, score-0.079]
27 rA o language nisc efo orfm aa sliyzmedb as a sinub wse its o nfo Σte∗d. [sent-37, score-0.126]
28 wLe|t Nn denote the set of vectors of positive integers of dimension n. [sent-38, score-0.064]
29 The i-th component of a vector x in Nn is x(i), 0 denotes the null vector, 1 vector with 1 values, and ei the vecthe tor with 1 as its i-th component and 0 everywhere else. [sent-39, score-0.233]
30 The ordering ≤ on Nn is the componentwise ordering: o xr ≤ y igff ≤ x(i) ≤ y(i) for all 0 < i ≤ n. [sent-40, score-0.087]
wordName wordTfidf (topN-words)
[('mligs', 0.451), ('emptiness', 0.346), ('repariert', 0.282), ('rambow', 0.248), ('dominance', 0.248), ('formalisms', 0.194), ('membership', 0.191), ('repaired', 0.148), ('grammars', 0.124), ('dass', 0.113), ('fridgeacc', 0.113), ('heute', 0.113), ('minimalist', 0.113), ('peternom', 0.113), ('petri', 0.113), ('rediscovered', 0.113), ('uhlschrank', 0.113), ('complexity', 0.099), ('sylvain', 0.099), ('ens', 0.099), ('links', 0.096), ('lichte', 0.091), ('nets', 0.091), ('scrambling', 0.091), ('den', 0.083), ('today', 0.082), ('hat', 0.08), ('becker', 0.077), ('survey', 0.074), ('complements', 0.071), ('peter', 0.069), ('nn', 0.064), ('logic', 0.061), ('productions', 0.059), ('indexed', 0.057), ('shortest', 0.055), ('formalism', 0.049), ('nisc', 0.049), ('tih', 0.049), ('fridge', 0.049), ('everywhere', 0.049), ('candito', 0.049), ('cnrs', 0.049), ('groote', 0.049), ('stabler', 0.049), ('xf', 0.049), ('atb', 0.045), ('sov', 0.045), ('satisfiability', 0.045), ('reused', 0.045), ('aisn', 0.045), ('xr', 0.045), ('wle', 0.045), ('turns', 0.043), ('notorious', 0.042), ('nfo', 0.042), ('unordered', 0.042), ('cof', 0.042), ('inspiring', 0.042), ('multiplicative', 0.042), ('ordering', 0.042), ('ei', 0.041), ('linguistically', 0.04), ('motivating', 0.04), ('nominative', 0.04), ('ael', 0.04), ('finite', 0.039), ('flexible', 0.039), ('linear', 0.039), ('vector', 0.038), ('move', 0.037), ('fer', 0.037), ('yo', 0.037), ('accusative', 0.037), ('lexicalization', 0.037), ('uncertain', 0.035), ('affairs', 0.035), ('concluding', 0.035), ('efo', 0.035), ('pv', 0.035), ('tor', 0.034), ('france', 0.034), ('enforced', 0.034), ('dn', 0.034), ('integers', 0.033), ('unsurprisingly', 0.033), ('denotes', 0.033), ('german', 0.033), ('hpsg', 0.032), ('mechanisms', 0.032), ('sv', 0.032), ('questions', 0.031), ('vectors', 0.031), ('motivated', 0.031), ('broader', 0.03), ('notations', 0.03), ('emphasis', 0.03), ('illustration', 0.03), ('contextfree', 0.03), ('open', 0.029)]
simIndex simValue paperId paperTitle
same-paper 1 0.99999988 182 acl-2010-On the Computational Complexity of Dominance Links in Grammatical Formalisms
Author: Sylvain Schmitz
Abstract: Dominance links were introduced in grammars to model long distance scrambling phenomena, motivating the definition of multiset-valued linear indexed grammars (MLIGs) by Rambow (1994b), and inspiring quite a few recent formalisms. It turns out that MLIGs have since been rediscovered and reused in a variety of contexts, and that the complexity of their emptiness problem has become the key to several open questions in computer science. We survey complexity results and open issues on MLIGs and related formalisms, and provide new complexity bounds for some linguistically motivated restrictions.
2 0.13509609 260 acl-2010-Wide-Coverage NLP with Linguistically Expressive Grammars
Author: Julia Hockenmaier ; Yusuke Miyao ; Josef van Genabith
Abstract: unkown-abstract
3 0.088570505 67 acl-2010-Computing Weakest Readings
Author: Alexander Koller ; Stefan Thater
Abstract: We present an efficient algorithm for computing the weakest readings of semantically ambiguous sentences. A corpus-based evaluation with a large-scale grammar shows that our algorithm reduces over 80% of sentences to one or two readings, in negligible runtime, and thus makes it possible to work with semantic representations derived by deep large-scale grammars.
4 0.050780348 66 acl-2010-Compositional Matrix-Space Models of Language
Author: Sebastian Rudolph ; Eugenie Giesbrecht
Abstract: We propose CMSMs, a novel type of generic compositional models for syntactic and semantic aspects of natural language, based on matrix multiplication. We argue for the structural and cognitive plausibility of this model and show that it is able to cover and combine various common compositional NLP approaches ranging from statistical word space models to symbolic grammar formalisms.
5 0.039520837 211 acl-2010-Simple, Accurate Parsing with an All-Fragments Grammar
Author: Mohit Bansal ; Dan Klein
Abstract: We present a simple but accurate parser which exploits both large tree fragments and symbol refinement. We parse with all fragments of the training set, in contrast to much recent work on tree selection in data-oriented parsing and treesubstitution grammar learning. We require only simple, deterministic grammar symbol refinement, in contrast to recent work on latent symbol refinement. Moreover, our parser requires no explicit lexicon machinery, instead parsing input sentences as character streams. Despite its simplicity, our parser achieves accuracies of over 88% F1 on the standard English WSJ task, which is competitive with substantially more complicated state-of-theart lexicalized and latent-variable parsers. Additional specific contributions center on making implicit all-fragments parsing efficient, including a coarse-to-fine inference scheme and a new graph encoding.
6 0.03858161 228 acl-2010-The Importance of Rule Restrictions in CCG
7 0.037169356 4 acl-2010-A Cognitive Cost Model of Annotations Based on Eye-Tracking Data
8 0.035513289 213 acl-2010-Simultaneous Tokenization and Part-Of-Speech Tagging for Arabic without a Morphological Analyzer
9 0.035389654 217 acl-2010-String Extension Learning
10 0.033975471 46 acl-2010-Bayesian Synchronous Tree-Substitution Grammar Induction and Its Application to Sentence Compression
11 0.033888474 24 acl-2010-Active Learning-Based Elicitation for Semi-Supervised Word Alignment
12 0.033510894 186 acl-2010-Optimal Rank Reduction for Linear Context-Free Rewriting Systems with Fan-Out Two
13 0.031753529 70 acl-2010-Contextualizing Semantic Representations Using Syntactically Enriched Vector Models
14 0.031025501 87 acl-2010-Discriminative Modeling of Extraction Sets for Machine Translation
15 0.030665156 133 acl-2010-Hierarchical Search for Word Alignment
16 0.0305587 203 acl-2010-Rebanking CCGbank for Improved NP Interpretation
17 0.030342842 128 acl-2010-Grammar Prototyping and Testing with the LinGO Grammar Matrix Customization System
18 0.027952263 130 acl-2010-Hard Constraints for Grammatical Function Labelling
19 0.027880456 200 acl-2010-Profiting from Mark-Up: Hyper-Text Annotations for Guided Parsing
20 0.027858566 84 acl-2010-Detecting Errors in Automatically-Parsed Dependency Relations
topicId topicWeight
[(0, -0.071), (1, -0.014), (2, 0.016), (3, -0.029), (4, -0.038), (5, -0.039), (6, 0.063), (7, 0.015), (8, 0.052), (9, -0.041), (10, 0.02), (11, -0.003), (12, -0.034), (13, 0.025), (14, -0.05), (15, 0.021), (16, -0.004), (17, 0.014), (18, -0.04), (19, 0.034), (20, 0.021), (21, -0.024), (22, -0.026), (23, -0.04), (24, 0.063), (25, -0.02), (26, -0.061), (27, 0.034), (28, 0.028), (29, 0.003), (30, -0.04), (31, -0.03), (32, -0.089), (33, 0.056), (34, -0.012), (35, 0.07), (36, -0.026), (37, -0.049), (38, 0.048), (39, 0.001), (40, -0.067), (41, -0.015), (42, 0.028), (43, -0.02), (44, -0.021), (45, 0.014), (46, -0.056), (47, -0.026), (48, 0.151), (49, -0.219)]
simIndex simValue paperId paperTitle
same-paper 1 0.9654488 182 acl-2010-On the Computational Complexity of Dominance Links in Grammatical Formalisms
Author: Sylvain Schmitz
Abstract: Dominance links were introduced in grammars to model long distance scrambling phenomena, motivating the definition of multiset-valued linear indexed grammars (MLIGs) by Rambow (1994b), and inspiring quite a few recent formalisms. It turns out that MLIGs have since been rediscovered and reused in a variety of contexts, and that the complexity of their emptiness problem has become the key to several open questions in computer science. We survey complexity results and open issues on MLIGs and related formalisms, and provide new complexity bounds for some linguistically motivated restrictions.
2 0.62647671 67 acl-2010-Computing Weakest Readings
Author: Alexander Koller ; Stefan Thater
Abstract: We present an efficient algorithm for computing the weakest readings of semantically ambiguous sentences. A corpus-based evaluation with a large-scale grammar shows that our algorithm reduces over 80% of sentences to one or two readings, in negligible runtime, and thus makes it possible to work with semantic representations derived by deep large-scale grammars.
3 0.57068235 260 acl-2010-Wide-Coverage NLP with Linguistically Expressive Grammars
Author: Julia Hockenmaier ; Yusuke Miyao ; Josef van Genabith
Abstract: unkown-abstract
4 0.50408459 128 acl-2010-Grammar Prototyping and Testing with the LinGO Grammar Matrix Customization System
Author: Emily M. Bender ; Scott Drellishak ; Antske Fokkens ; Michael Wayne Goodman ; Daniel P. Mills ; Laurie Poulson ; Safiyyah Saleem
Abstract: This demonstration presents the LinGO Grammar Matrix grammar customization system: a repository of distilled linguistic knowledge and a web-based service which elicits a typological description of a language from the user and yields a customized grammar fragment ready for sustained development into a broad-coverage grammar. We describe the implementation of this repository with an emphasis on how the information is made available to users, including in-browser testing capabilities.
5 0.4536747 234 acl-2010-The Use of Formal Language Models in the Typology of the Morphology of Amerindian Languages
Author: Andres Osvaldo Porta
Abstract: The aim of this work is to present some preliminary results of an investigation in course on the typology of the morphology of the native South American languages from the point of view of the formal language theory. With this object, we give two contrasting examples of descriptions of two Aboriginal languages finite verb forms morphology: Argentinean Quechua (quichua santiague n˜o) and Toba. The description of the morphology of the finite verb forms of Argentinean quechua, uses finite automata and finite transducers. In this case the construction is straightforward using two level morphology and then, describes in a very natural way the Argentinean Quechua morphology using a regular language. On the contrary, the Toba verbs morphology, with a system that simultaneously uses prefixes and suffixes, has not a natural description as regular language. Toba has a complex system of causative suffixes, whose successive applications determinate the use of prefixes belonging different person marking prefix sets. We adopt the solution of Creider et al. (1995) to naturally deal with this and other similar morphological processes which involve interactions between prefixes and suffixes and then we describe the toba morphology using linear context-free languages.1 .
6 0.44920799 66 acl-2010-Compositional Matrix-Space Models of Language
7 0.39778379 222 acl-2010-SystemT: An Algebraic Approach to Declarative Information Extraction
8 0.39099991 228 acl-2010-The Importance of Rule Restrictions in CCG
9 0.36626157 235 acl-2010-Tools for Multilingual Grammar-Based Translation on the Web
10 0.34574777 7 acl-2010-A Generalized-Zero-Preserving Method for Compact Encoding of Concept Lattices
11 0.33445257 92 acl-2010-Don't 'Have a Clue'? Unsupervised Co-Learning of Downward-Entailing Operators.
12 0.31983757 197 acl-2010-Practical Very Large Scale CRFs
13 0.31701791 95 acl-2010-Efficient Inference through Cascades of Weighted Tree Transducers
14 0.30617416 186 acl-2010-Optimal Rank Reduction for Linear Context-Free Rewriting Systems with Fan-Out Two
15 0.2791357 139 acl-2010-Identifying Generic Noun Phrases
16 0.27376723 35 acl-2010-Automated Planning for Situated Natural Language Generation
17 0.27018824 255 acl-2010-Viterbi Training for PCFGs: Hardness Results and Competitiveness of Uniform Initialization
18 0.26814312 162 acl-2010-Learning Common Grammar from Multilingual Corpus
19 0.25599939 23 acl-2010-Accurate Context-Free Parsing with Combinatory Categorial Grammar
20 0.25297543 40 acl-2010-Automatic Sanskrit Segmentizer Using Finite State Transducers
topicId topicWeight
[(4, 0.016), (14, 0.01), (21, 0.472), (25, 0.051), (33, 0.026), (42, 0.021), (59, 0.027), (73, 0.038), (76, 0.016), (78, 0.042), (83, 0.068), (84, 0.018), (98, 0.086)]
simIndex simValue paperId paperTitle
same-paper 1 0.82751501 182 acl-2010-On the Computational Complexity of Dominance Links in Grammatical Formalisms
Author: Sylvain Schmitz
Abstract: Dominance links were introduced in grammars to model long distance scrambling phenomena, motivating the definition of multiset-valued linear indexed grammars (MLIGs) by Rambow (1994b), and inspiring quite a few recent formalisms. It turns out that MLIGs have since been rediscovered and reused in a variety of contexts, and that the complexity of their emptiness problem has become the key to several open questions in computer science. We survey complexity results and open issues on MLIGs and related formalisms, and provide new complexity bounds for some linguistically motivated restrictions.
2 0.37890646 172 acl-2010-Minimized Models and Grammar-Informed Initialization for Supertagging with Highly Ambiguous Lexicons
Author: Sujith Ravi ; Jason Baldridge ; Kevin Knight
Abstract: We combine two complementary ideas for learning supertaggers from highly ambiguous lexicons: grammar-informed tag transitions and models minimized via integer programming. Each strategy on its own greatly improves performance over basic expectation-maximization training with a bitag Hidden Markov Model, which we show on the CCGbank and CCG-TUT corpora. The strategies provide further error reductions when combined. We describe a new two-stage integer programming strategy that efficiently deals with the high degree of ambiguity on these datasets while obtaining the full effect of model minimization.
3 0.27437264 71 acl-2010-Convolution Kernel over Packed Parse Forest
Author: Min Zhang ; Hui Zhang ; Haizhou Li
Abstract: This paper proposes a convolution forest kernel to effectively explore rich structured features embedded in a packed parse forest. As opposed to the convolution tree kernel, the proposed forest kernel does not have to commit to a single best parse tree, is thus able to explore very large object spaces and much more structured features embedded in a forest. This makes the proposed kernel more robust against parsing errors and data sparseness issues than the convolution tree kernel. The paper presents the formal definition of convolution forest kernel and also illustrates the computing algorithm to fast compute the proposed convolution forest kernel. Experimental results on two NLP applications, relation extraction and semantic role labeling, show that the proposed forest kernel significantly outperforms the baseline of the convolution tree kernel. 1
4 0.26814723 75 acl-2010-Correcting Errors in a Treebank Based on Synchronous Tree Substitution Grammar
Author: Yoshihide Kato ; Shigeki Matsubara
Abstract: This paper proposes a method of correcting annotation errors in a treebank. By using a synchronous grammar, the method transforms parse trees containing annotation errors into the ones whose errors are corrected. The synchronous grammar is automatically induced from the treebank. We report an experimental result of applying our method to the Penn Treebank. The result demonstrates that our method corrects syntactic annotation errors with high precision.
5 0.26811957 153 acl-2010-Joint Syntactic and Semantic Parsing of Chinese
Author: Junhui Li ; Guodong Zhou ; Hwee Tou Ng
Abstract: This paper explores joint syntactic and semantic parsing of Chinese to further improve the performance of both syntactic and semantic parsing, in particular the performance of semantic parsing (in this paper, semantic role labeling). This is done from two levels. Firstly, an integrated parsing approach is proposed to integrate semantic parsing into the syntactic parsing process. Secondly, semantic information generated by semantic parsing is incorporated into the syntactic parsing model to better capture semantic information in syntactic parsing. Evaluation on Chinese TreeBank, Chinese PropBank, and Chinese NomBank shows that our integrated parsing approach outperforms the pipeline parsing approach on n-best parse trees, a natural extension of the widely used pipeline parsing approach on the top-best parse tree. Moreover, it shows that incorporating semantic role-related information into the syntactic parsing model significantly improves the performance of both syntactic parsing and semantic parsing. To our best knowledge, this is the first research on exploring syntactic parsing and semantic role labeling for both verbal and nominal predicates in an integrated way. 1
6 0.26723257 17 acl-2010-A Structured Model for Joint Learning of Argument Roles and Predicate Senses
7 0.26593676 101 acl-2010-Entity-Based Local Coherence Modelling Using Topological Fields
8 0.26570806 211 acl-2010-Simple, Accurate Parsing with an All-Fragments Grammar
9 0.26561958 185 acl-2010-Open Information Extraction Using Wikipedia
10 0.26544711 109 acl-2010-Experiments in Graph-Based Semi-Supervised Learning Methods for Class-Instance Acquisition
11 0.26117921 84 acl-2010-Detecting Errors in Automatically-Parsed Dependency Relations
12 0.26114377 70 acl-2010-Contextualizing Semantic Representations Using Syntactically Enriched Vector Models
13 0.2610369 251 acl-2010-Using Anaphora Resolution to Improve Opinion Target Identification in Movie Reviews
14 0.26074731 46 acl-2010-Bayesian Synchronous Tree-Substitution Grammar Induction and Its Application to Sentence Compression
15 0.26031679 14 acl-2010-A Risk Minimization Framework for Extractive Speech Summarization
16 0.26031071 186 acl-2010-Optimal Rank Reduction for Linear Context-Free Rewriting Systems with Fan-Out Two
17 0.26018244 155 acl-2010-Kernel Based Discourse Relation Recognition with Temporal Ordering Information
18 0.25998974 158 acl-2010-Latent Variable Models of Selectional Preference
19 0.25973207 93 acl-2010-Dynamic Programming for Linear-Time Incremental Parsing
20 0.2596226 128 acl-2010-Grammar Prototyping and Testing with the LinGO Grammar Matrix Customization System