The Complexity of Recognition of Linguistically Adequate Dependency Grammars

Results of computational complexity exist for a wide range of phrase structure-based grammar formalisms, while there is an apparent lack of such results for dependency-based formalisms. We here adapt a result on the complexity of ID/LP-grammars to the dependency framework. Contrary to previous studies on heavily restricted dependency grammars, we prove that recognition (and thus, parsing) of linguistically adequate dependency grammars is NP-complete.

• Publication year

  1997

• Venue

  Annual Meeting of the Association for Computational Linguistics

• Publication date

  1997-07-07

• Fields of study

  Linguistics, Computer Science

• Identifiers
  DOI 10.3115/976909.979660arXiv cmp-lg/9709001
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Restricted Parallelism in Object-Oriented Lexical Parsing

  1996cited by this paper
• Book Reviews: Head-driven Phrase Structure Grammar and German in Head-driven Phrase-structure Grammar

  1996cited by this paper
• An Earley-type recognizer for dependency grammar

  1996cited by this paper
• English word grammar

  1995influential reference
• Introduction to Government and Binding Theory

  1991cited by this paper
• Slot Grammar: A System for Simpler Construction of Practical Natural Language Grammars

  1989influential reference
• A logical treatment of semi-free word order and bounded discontinuous constituency

  1989cited by this paper
• The case for lexicase

  1988cited by this paper
• Chart Parsing According to the Slot and Filler Principle

  1988cited by this paper
• PHRASAL VERBS AND THE CATEGORIES OF POSTPONEMENT

  1988cited by this paper
• Dependency Syntax: Theory and Practice

  1987cited by this paper
• Surface syntax of English

  1986cited by this paper
• On the Complexity of ID/LP Parsing

  1985cited by this paper
• An efficient context-free parsing algorithm

  1970cited by this paper
• An efficient context-free parsing algorithm

  1970cited by this paper
• Dependency Systems and Phrase-Structure Systems

  1965cited by this paper
• Éléments de syntaxe structurale

  1959cited by this paper
• Introduction to government

  1953cited by this paper

• Chapter 40 LFG and Dependency Grammar

  2022cites this paper
• Projectivity is the mathematical code of syntax: Comment on "Dependency distance: A new perspective on syntactic patterns in natural languages" by Haitao Liu et al.

  2017cites this paper
• Text Mining and Knowledge Discovery from Big Data: Challenges and Promise

  2016cites this paper
• Improvements to the performance and applicability of dependency parsing

  2015cites this paper
• Bilexical Dependencies as an Intermedium for Data-Driven and HPSG-Based Parsing

  2015cites this paper
• An Efficient Dynamic Oracle for Unrestricted Non-Projective Parsing

  2015cites this paper
• A Parsing Approach to SAT

  2014cites this paper
• Advances in Artificial Intelligence -- IBERAMIA 2014

  2014cites this paper
• 79. Parsing with Dependency Grammars

  2014cites this paper
• Predicting Linguistic Structure with Incomplete and Cross-Lingual Supervision

  2013cites this paper
• Shall We Play the Festschrift Game?

  2012cites this paper
• On Dependency Analysis via Contractions and Weighted FSTs

  2012cites this paper
• Dependency Grammar: Classification and Exploration

  2011cites this paper
• A framework for structured knowledge extraction and representation from natural language via deep sentence analysis

  2011cites this paper
• Text Mining and Information Extraction

  2010cites this paper
• Dependency Structures and

  2010cites this paper
• Non-Projective Dependency Parsing

  2010cites this paper
• A Transition-Based Parser for 2-Planar Dependency Structures

  2010cites this paper
• Non-Projective Dependency Parsing in Expected Linear Time

  2009cites this paper
• Wide-coverage parsing for Turkish

  2009cites this paper
• Synthesis Lectures on Human Language Technologies

  2009cites this paper
• The string-generative capacity of regular dependency languages

  2009cites this paper
• Hybrid Long-Distance Functional Dependency Parsing

  2009cites this paper
• Dependency Parsing

  2009cites this paper
• Lambda Calculus on Dependency Structures for a Wide-Coverage Grammar of Esperanto Making Deep Semantics More Robust

  2008cites this paper
• Chapter 1 Dependency Grammar : Classification and Exploration

  2008cites this paper
• Global Inference and Learning Algorithms for Multi-Lingual Dependency Parsing

  2008cites this paper
• Dependency-based machine translation and parallel parsing without the projectivity and edge-factoring assumptions. A white paper

  2007cites this paper
• On the Complexity of Non-Projective Data-Driven Dependency Parsing

  2007cites this paper
• FRAMEWORK AND RESOURCES FOR NATURAL LANGUAGE

  2007cites this paper
• FG 2007: The 12th conference on Formal Grammar Dublin, Ireland August 4-5, 2007

  2007cites this paper
• Dependency structures and lexicalized grammars

  2007cites this paper
• Framework and Resources for Natural Language Parser Evaluation

  2007influential citation
• Incremental Non-Projective Dependency Parsing

  2007cites this paper
• The string-generative capacity of regular dependency languages

  2007cites this paper
• Constraints on Non-Projective Dependency Parsing

  2006cites this paper
• Parsing with Dependency Grammars

  2006cites this paper
• The Text Mining Handbook: Advanced Approaches in Analyzing Unstructured Data

  2006cites this paper
• Discriminative learning and spanning tree algorithms for dependency parsing

  2006cites this paper
• Statistical parsing with non-local dependencies

  2005cites this paper
• Dependency Grammar and Dependency Parsing

  2005cites this paper
• Style Recognition Using Shallow Statistical Analysis 1

  2004cites this paper
• Fast, Deep-Linguistic Statistical Dependency Parsing

  2004cites this paper
• A robust and hybrid deep-linguistic theory applied to large-scale parsing

  2004cites this paper
• Combining shallow and deep processing for a robust, fast, deep-linguistic dependency parser

  2004cites this paper
• ESSLLI 2004 Workshop on Combining Shallow and Deep Processing for NLP

  2004cites this paper
• Extracting and using trace-free functional dependencies from the penn treebank to reduce parsing complexity

  2003cites this paper
• Natural language parsing with graded constraints

  2002cites this paper
• Separating Surface Order and Syntactic Relations in a Dependency Grammar

  2002cites this paper
• Grammaires de dŽpendance formelles et thŽorie Sens-Texte

  2001cites this paper
• Grammars for Local and Long Dependencies

  2001cites this paper
• Polarized Non-projective Dependency Grammars

  2001cites this paper
• Logical Aspects of Computational Linguistics

  2001cites this paper
• Proceedings of the Sixth Internatonal Workshop on Parsing Technologies

  2000cites this paper
• ANSWER EXTRACTION USING A DEPENDENCY GRAMMAR IN EXTRANS

  2000cites this paper
• Let’s Parsetalk — Message-Passing Protocols for Object-Oriented Parsing

  2000cites this paper
• A Finite-state Parser with Dependency Structure Output

  2000cites this paper
• DEPENDENCIES ON THE OTHER SIDE OF THE CURTAIN

  2000cites this paper
• A formal theory of dependency syntax with non-lexical units

  1999cites this paper
• Grading Knowledge

  1999cites this paper
• A Projection Architecture for Dependency Grammar and How It Compares to Lfg

  1998cites this paper
• #238: Separating Surface Order and Syntactic Relations in a Dependency Grammar Topic Areas: L2. Syntax and Parsing under Consideration for Other Conferences (specify)? None #238: Separating Surface Order and Syntactic Relations in a Dependency Grammar

  1998cites this paper
• Separating Surface Order and Syntactic Relations in a Dependency Grammar

  1998cites this paper
• Formal Aspects and Parsing Issues of Dependency Theory

  1998cites this paper
• A Projection Architecture for Dependency Grammar and How it Compares to LFG

  1998cites this paper
• Towards an implementable dependency grammar

  1998cites this paper
• Formal aspects and parsing issues of dependency theory

  1998cites this paper
• A Projection Architecture for Dependency Grammar and How it Compares to LFG

  1998cites this paper
• Unit Coordination and Gapping in Dependency Theory

  1998cites this paper
• Pseudo-Projectivity: A Polynomially Parsable Non-Projective Dependency Grammar

  1998cites this paper
• How to de ne a context-free backbone for DGs : An experiment in grammar conversionNorbert

  1998cites this paper
• How to define a context-free backbone for DGs: Implementing a DG in the LFG formalism

  1998cites this paper
• Pseudo-Projectivity, A Polynomially Parsable Non-Projective Dependency Grammar

  1998cites this paper
• Unit Coordination and Gapping in Dependency Theory

  1998cites this paper
• Message-passing Protocols for Real-world Parsing - An Object-oriented Model and its Preliminary Evaluation

  1997cites this paper
• Word Order without Phrase Structure: a Modal Logic for Dependency Grammar

  1997cites this paper