LFG Generation from Acyclic F-Structures is NP-Hard
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Dokumenter
- LFG Generation for Acyclic F-Structures
Forlagets udgivne version, 236 KB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Tidsskrift | Computational Linguistics |
Vol/bind | 47 |
Udgave nummer | 4 |
Sider (fra-til) | 939–946 |
Antal sider | 8 |
ISSN | 1530-9312 |
DOI | |
Status | Udgivet - 2021 |
ID: 271826966