LFG-Generation from Acyclic F-Structures is NP-Hard

Authors

  • Jürgen Wedekind University of Copenhagen
  • Ronald M. Kaplan Stanford University

Abstract

The universal generation problem for LFG grammars is the problem of determining whether a given grammar derives any terminal string with a given f-structure. It is known that this problem is  decidable for acyclic f-structures. In this brief note, we show that for those f-structures the problem is nonetheless intractable. This holds even for grammars that are off-line parsable.

 

Published

2024-11-22

Issue

Section

Squibs and Discussions

How to Cite

LFG-Generation from Acyclic F-Structures is NP-Hard. (2024). Computational Linguistics, 47(4). https://cljournal.org/index.php/cljournal/article/view/1942