On time hierarchies

ABSTRACT

For fixed k ≥ 2 we tighten the time hierarchy for k-tape Turing machines. Also for fixed k ≥ 2 we exhibit infinite hierarchies of languages recognizable by k-tape machines with increasing amount of time on the same amount of space.

REFERENCES

• 1: S.A. Cook and R.A. Reckhow: "Time-bounded random access machines", JCSS 7, 354-375 (1973)
• 2: J. Hartmanis, P.M. Lewis and R.E. Stearns: "Hierarchies of memory limited computations", IEEE-SWAT 1965, 179-190
• 3: F. C. Hennie , R. E. Stearns, Two-Tape Simulation of Multitape Turing Machines, Journal of the ACM (JACM), v.13 n.4, p.533-546, Oct. 1966 [doi>10.1145/321356.321362]
• 4: J.E. Hopcroft, W.J. Paul and L.G. Valiant: "On time versus space and related problems", IEEE-FOCS 1975, 57-64
• 5: Wolfgang J. Paul , Robert Endre Tarjan , James R. Celoni, Space bounds for a game on graphs, Proceedings of the eighth annual ACM symposium on Theory of computing, p.149-160, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803643]
• 6: S. Ruby and P.C. Fischer: "Translational methods and computational complexity", IEEE-SWAT 1965, 173-178
• 7: Komplexität von Entscheidungsproblemen, Ein Seminar, January 1976

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Complexity hierarchies

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

General Terms:
Algorithms, Theory