Minimalist Grammars with Unbounded Scrambling and Nondiscriminating Barriers Are NP-Hard
From MaRDI portal
Publication:3540133
DOI10.1007/978-3-540-88282-4_38zbMath1156.68435OpenAlexW76822433WikidataQ63379016 ScholiaQ63379016MaRDI QIDQ3540133
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
Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lexicalized non-local MCTAG with dominance links is NP-complete
- Disentangling Notions of Specifier Impenetrability: Late Adjunction, Islands, and Expressive Power
- Observations on Strict Derivational Minimalism
- Logical Aspects of Computational Linguistics
- Logical aspects of computational linguistics. 4th international conference, LACL 2001, Le Croisic, France, June 27--29, 2001. Proceedings
This page was built for publication: Minimalist Grammars with Unbounded Scrambling and Nondiscriminating Barriers Are NP-Hard