path systems and language recognition
Our main result, theorem 2, gives a bound on the storage required for a Turing machine to simulate certain time-bounded pushdown machines. The theorem is a generalization of the result appearing in [3] stating that any context-free language can be recognized by a deterministic Turing machine within storage (log n) 2 . We introduce a combinatorial object, called a path system , develop its theory briefly, and use the theory to prove both the result on pushdown machines and the result on context free languages, as well as a third result. The third result is the Theorem of Savitch [5] stating that a non-deterministic L(n) - storage bounded Turing machine can be simulated by a deterministic (L(n)) 2 - storage bounded Turing machine.
systems language recognition storage simulation general context log object theory use timing