Generation as Dependency Parsing

Natural-Language Generation from flat semantics is an NP-complete problem. This makes it necessary to develop algorithms that run with reasonable efficiency in practice despite the high worst-case complexity. We show how to convert TAG generation problems into dependency parsing problems, which is useful because optimizations in recent dependency parsers based on constraint programming tackle exactly the combinatorics that make generation hard. Indeed, initial experiments display promising runtimes.

• Publication year

  2002

• Venue

  Annual Meeting of the Association for Computational Linguistics

• Publication date

  2002-07-06

• Fields of study

  Computer Science

• Identifiers
  DOI 10.3115/1073083.1073088
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Configuration of Labeled Trees under Lexicalized Constraints and Principles

  2003cited by this paper
• Constraint programming in computational linguistics

  2002cited by this paper
• Topological Dependency Trees: A Constraint-Based Account of Linear Precedence

  2001cited by this paper
• Generating with a Grammar Based on Tree Descriptions: a Constraint-Based Approach

  2001influential reference
• An Efficient Chart Generator for (Semi-)Lexicalist Grammars

  2001cited by this paper
• Using TAGs, a Tree Model, and a Language Model for Generation

  2000cited by this paper
• A Lexicalized Tree Adjoining Grammar for English

  1998cited by this paper
• Tree-Adjoining Grammars

  1997cited by this paper
• Sentence Planning as Description Using Tree Adjoining Grammar

  1997cited by this paper
• Chart Generation

  1996cited by this paper
• An Alternative Conception of Tree-Adjoining Derivation

  1992cited by this paper
• Letting the Cat Out of the Bag: Generation for Shake-and-Bake MT

  1992cited by this paper
• A Lexicalized Tree Adjoining Grammar for English

  1990cited by this paper
• Computational complexity and natural language

  1987cited by this paper

• Handbook of Research on Natural Language Processing and Smart Service Systems

  2021cites this paper
• Issues in the Syntactic Parsing of Queries for a Natural Language Interface to Databases

  2021cites this paper
• Natural Language Interfaces to Databases

  2021cites this paper
• Advances in Natural Language Generation: Generating Varied Outputs from Semantic Inputs

  2018cites this paper
• Evaluating Globally Normalized Transition Based Neural Networks for Multilingual Natural Language Understanding

  2017cites this paper
• Parsing and Generation as Datalog Query Evaluation.

  2017cites this paper
• Conversation level syntax similarity metric

  2017cites this paper
• Integrated sentence generation using charts

  2017cites this paper
• An Ordinal-free Proof of the Complete Cut-elimination Theorem for \Pi^1_1-CA+BI with the omega-rule

  2017cites this paper
• Survey of the State of the Art in Natural Language Generation: Core tasks, applications and evaluation

  2017cites this paper
• From OpenCCG to AI Planning: Detecting Infeasible Edges in Sentence Generation

  2016cites this paper
• Paraphrase Generation from Latent-Variable PCFGs for Semantic Parsing

  2016cites this paper
• Syntax and Data-to-Text Generation

  2014cites this paper
• An ACG View on G-TAG and Its g-Derivation

  2014cites this paper
• Generating and Simplifying Sentences

  2014cites this paper
• Effective Parsing for Human Aided NLP Systems

  2013cites this paper
• KBGen - Text Generation for Knowledge Bases as a New Shared Task

  2012cites this paper
• Using genetic algorithms to create meaningful poetic text

  2012influential citation
• KBGen – Text Generation from Knowledge Bases as a New Shared Task

  2012cites this paper
• Structure-Driven Lexicalist Generation

  2012influential citation
• Dependency Grammar: Classification and Exploration

  2011cites this paper
• EXPERIENCES WITH PLANNING FOR NATURAL LANGUAGE GENERATION

  2011influential citation
• Using regular tree grammars to enhance sentence realisation

  2011cites this paper
• Domain proposal : Sentence generation with tree-adjoining grammars ( CRISP )

  2010cites this paper
• A Simple Domain-Independent Probabilistic Approach to Generation

  2010cites this paper
• Dependency Structures and

  2010cites this paper
• RTG based surface realisation for TAG

  2010influential citation
• Comparing the performance of two TAG-based surface realisers using controlled grammar traversal

  2010cites this paper
• Using regular tree grammars to optimise surface realisation

  2009cites this paper
• Parsing German Topological Fields with Probabilistic Context-Free Grammars

  2009cites this paper
• Extending a Surface Realizer to Generate Coherent Discourse

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

  2008influential citation
• An Implementation of a Flexible Author-Reviewer Model of Generation using Genetic Algorithms

  2008cites this paper
• Calculs d’unification sur les arbres de dérivation TAG

  2008cites this paper
• Derivation Trees of a Tree Adjoining Grammar

  2008cites this paper
• Logics and Automata for Totally Ordered Trees

  2008cites this paper
• Feature Unification in TAG Derivation Trees

  2008cites this paper
• Computational Linguistics and Theorem Proving in a Computer Game Seminar "Linguistic Inference and Textual Entailment"

  2007cites this paper
• Sentence generation as a planning problem

  2007cites this paper
• A Symbolic Approach to Near-Deterministic Surface Realisation using Tree Adjoining Grammar

  2007cites this paper
• Surface realisation: ambiguity and determinism

  2007influential citation
• Une réalisateur de surface basé sur une grammaire réversible

  2007cites this paper
• Dependency structures and lexicalized grammars

  2007cites this paper
• GenI, un réalisateur basé sur une grammaire réversible

  2007cites this paper
• GenI: natural language generation in Haskell

  2006cites this paper
• A Polynomial Parsing Algorithm for the Topological Model: Synchronizing Constituent and Dependency Grammars, Illustrated by German Word Order Phenomena

  2006cites this paper
• Extensible dependency grammar: a modular grammar formalism based on multigraph description

  2006cites this paper
• Three Reasons to Adopt TAG-Based Surface Realisation

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

  2005cites this paper
• Dependency Grammar as Multigraph Description

  2005cites this paper
• Adapting polarised disambiguation to surface realisation

  2005cites this paper
• Reconciling Parameterization, Configurability and Optimality in Natural Language Generation via Multiparadigm Programming

  2005cites this paper
• Proling the XDG Constraint Solver

  2005cites this paper
• Generating and Selecting Grammatical Paraphrases

  2005influential citation
• Flexibility, Configurability and Optimality in UNL Deconversion via Multiparadigm Programming

  2005cites this paper
• Optimising a Surface Realiser

  2004cites this paper
• Intention, interpretation and the computational structure of language

  2004cites this paper
• Taking Linguistic Dimensions More Seriously : The New Grammar Formalism of Extensible Dependency Grammar

  2004cites this paper
• Extensible Dependency Grammar: A New Methodology

  2004cites this paper
• Put My Galakmid Coin into the Dispenser and Kick It: Computational Linguistics and Theorem Proving in a Computer Game

  2004influential citation
• A Relational Syntax-Semantics Interface Based on Dependency Grammar

  2004cites this paper
• TAG Parsing as Model Enumeration

  2004influential citation
• Multiword Expressions as Dependency Subgraphs

  2004cites this paper
• Intention, Interpretation and the Computational Structure of Language

  2004cites this paper
• An evolutionary algorithm approach to poetry generation

  2004cites this paper
• Multi-dimensional Graph Configuration for Natural Language Processing

  2004influential citation
• Statistical A Dependency Parsing

  2004cites this paper
• Constraint-based and graph-based resolution of ambiguities in natural language

  2004cites this paper
• A parser system for extensible dependency grammar

  2003cites this paper
• Statistical A-star dependency parsing

  2003cites this paper
• Hybrid discourse modeling and summarization for a speech-to-speech translation system

  2003cites this paper
• Dependency grammar as graph description

  2003cites this paper
• Natural Language and Inference in a Computer Game

  2002cites this paper
• Anaphora and Discourse Structure

  2001cites this paper
• Project Mi 2: Chorus: Semantic Processing with Constraints and Preferences

  2001cites this paper
• An ACG View on G-TAG and Its g-Derivation ⋆

  year unknowncites this paper
• N : M Mapping in XDG The Case for Upgrading Groups

  year unknowncites this paper