  This paper examines several measures of space complexity of variants of stack
automata: non-erasing stack automata and checking stack automata. These
measures capture the minimum stack size required to accept every word in the
language of the automaton (weak measure), the maximum stack size used in any
accepting computation on any accepted word (accept measure),and the maximum
stack size used in any computation (strong measure). We give a detailed
characterization of the accept and strong space complexity measures for
checking stack automata. Exactly one of three cases can occur: the complexity
is either bounded by a constant, behaves like a linear function, or it can not
be bounded by any function of the length of the input word (and it is decidable
which case occurs). However, this result does not hold for non-erasing stack
automata; we provide an example where the space complexity grows proportionally
to the square root of the length of the input. Furthermore, we study the
complexity bounds of machines which accept a given language, and decidability
of space complexity properties.
