This paper tries to fully characterize the properties and relationships of space classes defined by Turing machines that use less than logarithmic space - may they be deterministic, nondeterministic or alternating (DTM, NTM or ATM). We provide several examples of specific languages and show that such machines are unable to ...
more >>>