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

DOI10.1007/978-3-540-88282-4_38MaRDI QIDQ3540133zbMATH OpenOpenAlexDBLPWikidataFDO

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

Mathematics Subject Classification ID

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

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

Cites work

• scientific article; zbMATH DE number 1689585 (Why is no real title available?)
• scientific article; zbMATH DE number 1786553 (Why is no real title available?)
• scientific article; zbMATH DE number 1786555 (Why is no real title available?)
• scientific article; zbMATH DE number 777478 (Why is no real title available?)
• Derivational minimalism
• Disentangling notions of specifier impenetrability: late adjunction, islands, and expressive power
• Lexicalized non-local MCTAG with dominance links is NP-complete
• Logical Aspects of Computational Linguistics
• Logical aspects of computational linguistics. 4th international conference, LACL 2001, Le Croisic, France, June 27--29, 2001. Proceedings
• Observations on strict derivational minimalism

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)