A note on the complexity of the recognition problem for the Minimalist Grammars with unbounded scrambling and barriers

• Autores: Alexander Perekrestenko
• Localización: Procesamiento del lenguaje natural, ISSN 1135-5948, Nº. 39, 2007, págs. 27-34
• Idioma: español
• Enlaces
  • Texto completo
• Resumen
  • español

    Las Gramáticas Minimalistas fueron introducidas recientemente como un modelo para la descripción formal de la sintaxis de los lenguajes naturales. En este artículo, se investiga una extensión no local de este formalismo que permitiría la descripción del desplazamiento optativo ilimitado de constituyentes sintácticos (scrambling), un fenómeno que existe en muchos idiomas y presenta dificultades para la descripción formal. Se establece que la extensión de las Gramáticas Minimalistas con scrambling sin la llamada condición del movimiento más corto (shortest-move constraint, SMC) y con barreras hace que el problema de reconocimiento para el formalismo resultante pertenezca a la clase NP-hard de la complejidad computacional.

  • English

    Minimalist Grammars were proposed recently as a model for the formal description of the natural-language syntax. This paper explores a nonlocal extension to this formalism that would make it possible to describe unbounded scrambling which is a discriptionally problematic syntactic phenomenon attested in many languages. It is shown that extending Minimalist Grammars with scrambling without shortest-move constraint (SMC) and with barriers makes the recognition problem for the resulting formalism NP-hard.