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
- 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)
- PDF:
- https://preview.aclanthology.org/ingestion-script-update/2021.cl-4.31.pdf