Techniques for separating space complexity classes

摘要

Diagonalization, cardinality, and recursive padding arguments are used to separate the Turing machine space complexity classes obtained by bounding space, number of worktape symbols, and number of worktape heads. Witness languages over a one-letter alphabet are constructed when possible.