Path systems and language recognition

ABSTRACT

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.

REFERENCES

• 1: Cook, S. A. and W. J. Savitch. "Mazes and Turing Machines". Technical Report No. 29, Computer Center, University of California, December, 1968.
• 2: Stephen A. Cook, Variations on pushdown machines (Detailed Abstract), Proceedings of the first annual ACM symposium on Theory of computing, p.229-231, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805437]
• 3: Lewis, P.M. II, R. E. Stearns, and J. Hartmanis. "Memory Bounds for the Recognition of Context-Free and Context Sensitive Languages." IEEE Conference Record on 1965 Symposium on Switching Circuit Theory and Logical Design.
• 4: Kreider, D. L. and R. W. Ritchie. "Predicatably Computable Functionals and Definitions by Recursion". Zeitschrift fur math. Logiks and Grundlagen der Math., Vol. 10, 65-80 (1964).
• 5: Walter John Savitch, Nondeterministic tape bounded turing machines, 1969

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Automata (e.g., finite, push-down, resource-bounded); Bounded-action devices (e.g., Turing machines, random access machines)
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)

General Terms:
Algorithms, Languages, Theory