Minimalist Grammars with Unbounded Scrambling and Nondiscriminating Barriers Are NP-Hard.
| Autor: | Perekrestenko, Alexander |
|---|---|
| Zdroj: | Language & Automata Theory & Applications; 2008, p421-432, 12p |
| Abstrakt: | Minimalist Grammars were proposed in [15] as a formalization of the basic structure-building component of the Minimalism Program, a syntactic framework introduced in [2] and [3]. In the present paper we investigate the effects of extending this formalism with an unrestricted scrambling operator together with nondiscriminating barriers. We show that the recognition problem for the resulting formalism NP-hard. The result presented here is a generalization of the result shown by the author in [14] for Minimalist Grammars with unrestricted scrambling and category-sensitive barriers. [ABSTRACT FROM AUTHOR] |
| Databáze: | Complementary Index |
| Externí odkaz: |
|