LFG Generation from Acyclic F-Structures is NP-Hard

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Standard

LFG Generation from Acyclic F-Structures is NP-Hard. / Wedekind, Jürgen; Kaplan, Ronald M.

I: Computational Linguistics, Bind 47, Nr. 4, 2021, s. 939–946.

Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt

Harvard

Wedekind, J & Kaplan, RM 2021, 'LFG Generation from Acyclic F-Structures is NP-Hard', Computational Linguistics, bind 47, nr. 4, s. 939–946. https://doi.org/10.1162/coli_a_00419

APA

Wedekind, J., & Kaplan, R. M. (2021). LFG Generation from Acyclic F-Structures is NP-Hard. Computational Linguistics, 47(4), 939–946. https://doi.org/10.1162/coli_a_00419

Vancouver

Wedekind J, Kaplan RM. LFG Generation from Acyclic F-Structures is NP-Hard. Computational Linguistics. 2021;47(4):939–946. https://doi.org/10.1162/coli_a_00419

Author

Wedekind, Jürgen ; Kaplan, Ronald M. / LFG Generation from Acyclic F-Structures is NP-Hard. I: Computational Linguistics. 2021 ; Bind 47, Nr. 4. s. 939–946.

Bibtex

@article{cbb671fc756b4dc897b4beafc72fef08,
title = "LFG Generation from Acyclic F-Structures is NP-Hard",
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.",
author = "J{\"u}rgen Wedekind and Kaplan, {Ronald M.}",
year = "2021",
doi = "10.1162/coli_a_00419",
language = "English",
volume = "47",
pages = "939–946",
journal = "Computational Linguistics",
issn = "1530-9312",
publisher = "MIT Press",
number = "4",

}

RIS

TY - JOUR

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

AU - Wedekind, Jürgen

AU - Kaplan, Ronald M.

PY - 2021

Y1 - 2021

N2 - 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.

AB - 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.

U2 - 10.1162/coli_a_00419

DO - 10.1162/coli_a_00419

M3 - Journal article

VL - 47

SP - 939

EP - 946

JO - Computational Linguistics

JF - Computational Linguistics

SN - 1530-9312

IS - 4

ER -

ID: 271826966