Relating refined space complexity classes

摘要

Refined Turing machine space complexity classes are defined by limiting all three of the resources space, worktape alphabet size, and number of worktape heads. Containment relations among the classes are proved and used to convert a few basic noncontainment relations to noncontainment relations of four more homogeneous types: “less space” (conventional classes), “fewer worktape symbols,” “one fewer worktape symbol,” and “fewer worktape heads.” Noncontainment results for both nondeterministic and deterministic classes of both binary and unary languages are obtained. One corollary is a unary language hierarchy theorem for two-way multihead finite automata.