LFG Generation from Acyclic F-Structures is NP-Hard
AbstractThe 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-stru...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
The MIT Press
2021-12-01
|
| Series: | Computational Linguistics |
| Online Access: | https://direct.mit.edu/coli/article/47/4/939/106929/LFG-Generation-from-Acyclic-F-Structures-is-NP |