On the Universal Generation Problem for Unification Grammars

Jürgen Wedekind

doi:10.1162/COLI a 00191

On the Universal Generation Problem for Unification Grammars

Jürgen Wedekind

Centre for Language Technology

1 Citation (Scopus)

Abstract

The universal generation problem for unification grammars is the problem of determining whether a given grammar derives any terminal string with a given feature structure. It is known that the problem is decidable for LFG and PATR grammars if only acyclic feature structures are taken into consideration. In this brief note, we show that the problem is undecidable for cyclic structures. This holds even for grammars that are off-line parsable.

Original language	English
Journal	Computational Linguistics
Volume	40
Issue number	3
Pages (from-to)	533-538
Number of pages	6
ISSN	1530-9312
DOIs	https://doi.org/10.1162/COLI a 00191
Publication status	Published - 1 Sept 2014

Access to Document

10.1162/COLI a 00191

http://www.mitpressjournals.org/doi/pdf/10.1162/COLI_a_00191

Cite this

@article{96c83841e7ec44b49612758cf56a92f7,

title = "On the Universal Generation Problem for Unification Grammars",

abstract = "The universal generation problem for unification grammars is the problem of determining whether a given grammar derives any terminal string with a given feature structure. It is known that the problem is decidable for LFG and PATR grammars if only acyclic feature structures are taken into consideration. In this brief note, we show that the problem is undecidable for cyclic structures. This holds even for grammars that are off-line parsable.",

author = "J{\"u}rgen Wedekind",

year = "2014",

month = sep,

day = "1",

doi = "10.1162/COLI a 00191",

language = "English",

volume = "40",

pages = "533--538",

journal = "Computational Linguistics",

issn = "1530-9312",

publisher = "MIT Press",

number = "3",

}

TY - JOUR

T1 - On the Universal Generation Problem for Unification Grammars

AU - Wedekind, Jürgen

PY - 2014/9/1

Y1 - 2014/9/1

N2 - The universal generation problem for unification grammars is the problem of determining whether a given grammar derives any terminal string with a given feature structure. It is known that the problem is decidable for LFG and PATR grammars if only acyclic feature structures are taken into consideration. In this brief note, we show that the problem is undecidable for cyclic structures. This holds even for grammars that are off-line parsable.

AB - The universal generation problem for unification grammars is the problem of determining whether a given grammar derives any terminal string with a given feature structure. It is known that the problem is decidable for LFG and PATR grammars if only acyclic feature structures are taken into consideration. In this brief note, we show that the problem is undecidable for cyclic structures. This holds even for grammars that are off-line parsable.

U2 - 10.1162/COLI a 00191

DO - 10.1162/COLI a 00191

M3 - Journal article

SN - 1530-9312

VL - 40

SP - 533

EP - 538

JO - Computational Linguistics

JF - Computational Linguistics

IS - 3

ER -

On the Universal Generation Problem for Unification Grammars

Abstract

Access to Document

Fingerprint

Cite this