Lower bounds on space complexity for contextfree recognition

Summary Using methods from linear algebra and crossing-sequence arguments it is shown that logarithmic space is necessary for the recognition of all context-free nonregular subsets of {a₁}^* ... {a_n}^*, where {a₁,...,a_n} is some alphabet. It then follows that log n is a lower bound on the space complexity for the recognition of any bounded or deterministic non-regular context-free language.