LFG Generation from Acyclic F-Structures is NP-Hard | Zendy

Jürgen Wedekind | Zendy; Ronald M. Kaplan | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

LFG Generation from Acyclic F-Structures is NP-Hard

Author(s) -

Jürgen Wedekind,

Ronald M. Kaplan

Publication year - 2021

Publication title -

computational linguistics

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.314

H-Index - 98

eISSN - 1530-9312

pISSN - 0891-2017

DOI - 10.1162/coli_a_00419

Subject(s) - rule based machine translation , decidability , string (physics) , computer science , grammar , tree adjoining grammar , combinatorics , programming language , discrete mathematics , theoretical computer science , context free grammar , mathematics , artificial intelligence , linguistics , philosophy , mathematical physics

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research