The notion of online space complexity, introduced by Karp in 1967, quantifies the amount of states required to solve a given problem using an online algorithm,
represented by a machine which scans the input exactly once from left to right.
In this paper, we study alternating machines as introduced by ... more >>>