Online Space Complexity

The notion of online space complexity, introduced by Karp in 1967, quantifies the amount of space required to solve a given problem using an online algorithm.
We devise a generic lower bound technique relying on boundedly generated lattices of languages, and two methods to apply it, one involving combinatorics on words and the other linear algebra. We give two applications of this technique.

The first is to prove that the polynomial hierarchy of alternating automata is infinite.

The second is to prove that the language of prime numbers written in binary does not have sublinear alternating online space complexity.
This strengthens a result of Hartmanis and Shank from 1968, which implied a logarithmic lower bound for the same model.
We obtain as a corollary that the primality of a number written in binary cannot be determined by a streaming alternating Turing machine using sublogarithmic space.