The goal of this research is to study space bounded computations. Even though space bounded computations are somewhat less difficult to analyze than time bounded computations, little is known regarding the power of nondeterminism. This research attempts to understand underlying combinatorics in space bounded computations by looking at various restricted models of computation. The DSPACE?log n! =? NSPACE?log n! problem is approached by considering different models such as sublog space bounded machines, universal traversal sequence and multihead two way finite state automaton. These restricted models of computation raise interesting questions with direct consequence to DSPACE?log n! =? NSPACE?log n! problem. This research concentrates on developing and using tools like communication complexity to show lower bounds on space requirement in these models with the hope of understanding the space bounded computations.
