LFG Generation from Acyclic F-Structures is NP-Hard

Jürgen Wedekind, Ronald M. Kaplan


Abstract
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.
Anthology ID:
2021.cl-4.31
Volume:
Computational Linguistics, Volume 47, Issue 4 - December 2021
Month:
December
Year:
2021
Address:
Cambridge, MA
Venue:
CL
SIG:
Publisher:
MIT Press
Note:
Pages:
939–946
Language:
URL:
https://aclanthology.org/2021.cl-4.31
DOI:
10.1162/coli_a_00419
Bibkey:
Cite (ACL):
Jürgen Wedekind and Ronald M. Kaplan. 2021. LFG Generation from Acyclic F-Structures is NP-Hard. Computational Linguistics, 47(4):939–946.
Cite (Informal):
LFG Generation from Acyclic F-Structures is NP-Hard (Wedekind & Kaplan, CL 2021)
Copy Citation:
PDF:
https://preview.aclanthology.org/ingestion-script-update/2021.cl-4.31.pdf