Minimalist Grammars with Unbounded Scrambling and Nondiscriminating Barriers Are NP-Hard

DOI10.1007/978-3-540-88282-4_38zbMATH Open1156.68435DBLPconf/lata/Perekrestenko08OpenAlexW76822433WikidataQ63379016 ScholiaQ63379016MaRDI QIDQ3540133FDOQ3540133

Authors: Alexander Perekrestenko 

Publication date: 20 November 2008

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-88282-4_38

Recommendations

• Lexicalized non-local MCTAG with dominance links is NP-complete
• Logical Aspects of Computational Linguistics
• scientific article; zbMATH DE number 1786553
• Minimalist grammars in the light of logic
• Minimalist Grammars and Minimalist Categorial Grammars: Toward Inclusion of Generated Languages

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Grammars and rewriting systems (68Q42)

Cites Work

• Title not available (Why is that?)
• Derivational minimalism
• Title not available (Why is that?)
• Logical aspects of computational linguistics. 4th international conference, LACL 2001, Le Croisic, France, June 27--29, 2001. Proceedings
• Lexicalized non-local MCTAG with dominance links is NP-complete
• Title not available (Why is that?)
• Title not available (Why is that?)
• Observations on strict derivational minimalism
• Disentangling notions of specifier impenetrability: late adjunction, islands, and expressive power
• Logical Aspects of Computational Linguistics

Cited In (1)

• Lexicalized non-local MCTAG with dominance links is NP-complete

This page was built for publication: Minimalist Grammars with Unbounded Scrambling and Nondiscriminating Barriers Are NP-Hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3540133)