On deterministic context-free languages, multihead automata, and the power of an auxiliary pushdown store

ABSTRACT

A deterministic context-free language L0 is described which is log(n)-complete for the family of languages recognized by deterministic log(n)- tape bounded auxiliary pushdown automata in polynomial time. It follows that L0 is a “hardest” deterministic context-free language (DCFL), since all DCFL's are recognized in polynomial time by deterministic pushdown automata. L0 is, moreover, a simple precedence language and a simple LL(1) language. Thus the tape complexities of these proper subfamilies are essentially the same as the tape complexity of all DCFL's. We show that an auxiliary pushdown store does, in fact, add some power to some restricted families of log(n)-tape bounded Turing machines. The basic result is that every two-way 2k-head nondeterministic finite automation can be replaced by an equivalent two-way k-head nondeterministic pushdown automation. This indicates, also, that every 2k-head nondeterministic finite automation language can be recognized in 0(n3k) steps. Other results relate multihead automata classes with other multihead automata classes, with families recognized by log(n)-tape bounded Turing machines with restricted tape alphabets, and with time-bounded complexity classes.

REFERENCES

• 1: Lynch, N., "Log Space Recognition and Translation of Parenthesis Languages," Technical Report, Mathematics Department, University of Southern California, Los Angeles, California 90007
• 2: Robert McNaughton, Parenthesis Grammars, Journal of the ACM (JACM), v.14 n.3, p.490-500, July 1967 [doi>10.1145/321406.321411]
• 3: I. H. Sudborough, A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages, Journal of the ACM (JACM), v.22 n.4, p.499-500, Oct. 1975 [doi>10.1145/321906.321913]
• 4: Savitch, W. J., "Relationships Between Non-deterministic and Deterministic Tape Complexities," J. Computer and System Sci. 4 (1970). pp. 177-192.
• 5: Stephen A. Cook, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, Journal of the ACM (JACM), v.18 n.1, p.4-18, Jan. 1971 [doi>10.1145/321623.321625]
• 6: Cook, S. A., "An Observation on Time-Storage Trade Off," J. Computer and System Sci. 9, 4 (1974). pp. 308-316.
• 7: Stephen Cook , Ravi Sethi, Storage requirements for deterministic / polynomial time recognizable languages, Proceedings of the sixth annual ACM symposium on Theory of computing, p.33-39, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803882]
• 8: Neil D. Jones , William T. Laaser, Complete problems for deterministic polynomial time, Proceedings of the sixth annual ACM symposium on Theory of computing, p.40-46, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803883]
• 9: Book, R. V., "Translational Lemmas, Polynomial Time, and (Log(n))j-Space," Technical Report, Department of Computer Science, Yale University.
• 10: Galil, Z., "Two-Way Deterministic Pushdown Automation Languages and Some Open Problems in the Theory of Computation," 15th Annual IEEE Symposium on Switching and Automata Theory (1974), pp. 170-177.
• 11: Lewis, P. M., R. E. Stearns and J. Hartmanis, "Memory Bounds for the Recognition of Context-Free and Context-Sensitive Languages," 6th Annual IEEE Symposium on Switching Circuit Theory and Logical Design (1965), pp. 199-212.
• 12: Greibach, S. A., "The Hardest Context-Free Language," SIAM J. on Computing 2, 4 (1973), pp. 304-310.
• 13: Korenjak, A. J. and J. E. Hopcroft, "Simple Deterministic Languages," 7th Annual IEEE Symposium on Switching and Automata Theory (1966), pp. 36-46.
• 14: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 15: Niklaus Wirth , Helmut Weber, EULER: a generalization of ALGOL and it formal definition: Part 1, Communications of the ACM, v.9 n.1, p.13-25, Jan. 1966 [doi>10.1145/365153.365162]
• 16: Michael J. Fischer, Some properties of precedence languages, Proceedings of the first annual ACM symposium on Theory of computing, p.181-190, May 05-07, 1969, Marina del Rey, California, United States [doi>10.1145/800169.805432]
• 17: Robert W. Floyd, Syntactic Analysis and Operator Precedence, Journal of the ACM (JACM), v.10 n.3, p.316-333, July 1963 [doi>10.1145/321172.321179]
• 18: Ibarra, O. H., "On Two-Way Multihead Automata," J. of Computer and System Sci. 7,1 (1973), pp. 28-36.
• 19: J. Seiferas, NONDETERMINISTIC TIME AND SPACE COMPLEXITY CLASSES, Massachusetts Institute of Technology, Cambridge, MA, 1974
• 20: Aho, A. V., J. E. Hopcroft and J. D. Ullman, "On the Computational Power of Pushdown Automata," J. Computer and System Sci. 4, 2 (1970), pp. 129-136.
• 21: Aho, A. V., J. E. Hopcroft and J. D. Ullman, "Time and Tape Complexity of Pushdown Automation Languages," Info. and Control 13,3 (1968), pp. 186-206.
• 22: Cook, S. A., "Linear Time Simulation of Deterministic Two-Way Pushdown Automata," Proceedings of IFIP Congress (1971), North-Holland Publishers.
• 23: Hartmanis, J., "On Non-Determinancy in Simple Computing Devices," Acta Informatica 1 (1972), pp. 336-344.
• 24: Valiant, L., "General Context-Free Recognition in Less Than Cubic Time," J. Computer and System Sci. 10, 2 (1975), pp. 308-315.
• 25: Sudborough, I. H., "On Tape-Bounded Complexity Classes and Multihead Finite Automata," J. Computer and System Sci. 10, 1 (1975), pp. 62-76.
• 26: Strassen, V., "Gaussian Elimination is Not Optimal," Numer. Math. 13 (1969), pp. 354-356.
• 27: Flajolet, P. and J. M. Steyaert, "Decision Problems for Multihead Finite Automata," Proceedings of Symposium and Summer School on the Mathematical Foundations of Computer Science, held in the High Tatros, Czechoslavakia (1973), pp. 225-230.
• 28: Beeri, C., "Reductions in the Number of Heads for the Nondeterminancy Problem in Multihead Automata," Technical Report, Institute of Mathematics, The Hebrew University of Jerusalem, Israel.
• 29: Lipton, R. J. and Y. Zalcstein, "Word Problems Solvable in Logspace," to be published.
• 30: Jones, N. D., "Space-Bounded Reducibility among Combinatorial Problems," Journal of Computer and System Sciences 11, 1 (1975), pp. 68-85.
• 31: L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804029]
• 32: VanLeeuwen, J., "The Tape Complexity of Context-Independent Developmental Languages," Journal of Computer and System Sciences 11, 2 (1975), pp. 203-211.
• 33: Ibarra, O. H., "Simple Matrix Languages," Information and Control 17 (1970), pp. 359-394.
• 34: Kasai, T., "An Hierarchy Between Context-Free and Context-Sensitive Languages," Journal of Computer and System Sciences 4 (1970), pp. 492-508.
• 35: Khabbaz, N. A., "A Geometric Hierarchy of Languages," Journal of Computer and System Sciences 8 (1974), pp. 142-157.
• 36: Kameda, T., "Pushdown Automata with Counters," Journal of Computer and System Sciences 6 (1972), pp. 138-150.
• 37: Sudborough, I. H., "On the Tape Complexity of Deterministic Context-Free Languages," submitted for publication.
• 38: Sudborough, I. H., "On the Computational Complexity of Multihead Automata Languages," submitted for publication.
• 39: Sudborough, I. H. and A. Arora, "On Languages Log-Tape Reducible to Context-Free Languages," proceedings of 1976 Conference on Information Sciences and Systems at Johns Hopkins University.
• 40: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  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)

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)

General Terms:
Languages, Theory