El análisis para formalismos de lenguaje ligeramente sensibles al contexto es un área importante dentro del procesamiento del lenguaje natural. Mientras que la complejidad del problema de análisis para algunos de estos formalismos se sabe que es polinómica, este no es el caso para todos ellos. Este artículo presenta una serie de resultados sobre la complejidad del análisis para sistemas de reescritura lineal context-libres y transductores deterministas de caminata en árboles. Discutimos la diferencia entre medidas de complejidad uniforme y no uniforme y cómo la teoría de complejidad parametrizada puede ser utilizada para investigar cómo diferentes aspectos de los formalismos influyen en la dificultad del problema de análisis. Los principales resultados que revisamos son todos resultados de dificultad e indican que el análisis es difícil incluso para valores relativamente pequeños de parámetros como rango y fan-out en un sistema de reescritura.