On the complexity of grammar and related problems

ABSTRACT

In [1] and [2] a complexity theory for formal languages and automata was developed. This theory implies most of the previously known results and yields many new results as well. Here we develop an analogous theory for several classes of more practically motivated problems. Two such classes, both closely related to formal language and automata theory, suggest themselves - grammar problems and program scheme problems. Here, our primary emphasis is on grammar problems of interest in parsing and compiling. Other problems considered include - (1) possible techniques for proving non-trivial lower complexity bounds for problems in P; (2) the relationship of the complexity of tree automaton equivalence, structural equivalence, and grammatical covering; and (3) the complexity of the equivalence problem for schemes. In each case we relate the computational complexity of a problem to its underlying combinatorial structure. The remainder of the paper is divided into four sections.

REFERENCES

• 1: Harry Bowen Hunt, III, On the time and tape complexity of languages., 1973
• 2: H. B. Hunt, III , D. J. Rosenkrantz, Computational parallels between the regular and context-free languages, Proceedings of the sixth annual ACM symposium on Theory of computing, p.64-74, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803885]
• 3: D. E. Knuth, On the translation of languages from left to right, Inf. and Cont. 8, 6 (1965), 607-639.
• 4: W. F. Ogden, unpublished note (Dec. 1971).
• 5: Harry B. Hunt, III , Thomas G. Szymanski , Jeffrey D. Ullman, On the complexity of LR(k) testing, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.130-136, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512990]
• 6: Thomas Gregory Szymanski, Generalized bottom-up parsing., 1973
• 7: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 8: W. J. Savitch, Relationships between non-deterministic and deterministic tape complexity, JCSS 4, 2 (1970), 177-192.
• 9: J. Hartmanis and H. B. Hunt, III, The lba problem and its importance in the theory of computing, SIAM-AMS Proc., Vol. 7, Amer. Math. Soc., Providence, R.I., 1974.
• 11: I. H. Sudborough, On tape-bounded complexity classes and multi-head finite automata, Proc. 14th An. IEEE Symp. on Switching and Automata Th. (Oct. 1973), 138-144.
• 12: 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]
• 13: Stephen A. Cook, An observation on time-storage trade off, Proceedings of the fifth annual ACM symposium on Theory of computing, p.29-33, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804032]
• 14: 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]
• 15: A. V. Aho, J. E. Hopcroft, and J. D. Ullman, Time and tape complexity of pushdown automaton languages, Inf. and Cont. 13, 3 (1968), 186-206.
• 16: T. G. Szymanski and J. H. Williams, Non-canonical parsing, Proc. 14th An. IEEE Symp. on Switching and Automata Th. (Oct. 1973), 122-129.
• 17: W. F. Ogden, A helpful result for proving inherent ambiguity, Math. Systems Th. 2, 3 (1968), 191-194.
• 18: J. E. Hopcroft, On the equivalence and containment problems for context-free languages, Math. Systems Th. 3, 2 (1969), 119-124.
• 19: M. A. Harrison and I. M. Havel, Strict deterministic grammars, JCSS 7, 3 (1973), 237-277.
• 20: B. M. Brosgol, Deterministic translation grammars, Ph.D. thesis, Harvard University, 1974.
• 21: K. Culik, II and R. Cohen, LR-regular grammars-an extension of LR(k) grammars, JCSS 7, 1 (1973), 66-96.
• 22: C. N. Fischer, Extended abstract - an approach to parallel parsing, unpublished.
• 23: J. Hartmanis , J. E. Hopcroft, An Overview of the Theory of Computational Complexity, Journal of the ACM (JACM), v.18 n.3, p.444-475, July 1971 [doi>10.1145/321650.321661]
• 24: H. B. Hunt, III, T. G. Szymanski, and J. D. Ullman, Operations on sparse relations and efficient algorithms for grammar problems, Proc. 15th An. IEEE Symp. on Switching and Automata Th. (Oct. 1974), 127-132.
• 25: H. B. Hunt, III, On the complexity of finite, pushdown, and stack automata, Mathematics Research Center Technical Summary Report #1504, University of Wisconsin-Madison, Oct. 1974 (also submitted for publication).
• 26: 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]
• 27: Alfred V. Aho, Nested Stack Automata, Journal of the ACM (JACM), v.16 n.3, p.383-406, July 1969 [doi>10.1145/321526.321529]
• 28: M. J. Fischer, Grammars with macro-like productions, Conf. Rec. 9th An. IEEE Symp. on Switching and Automata Th. (Oct. 1968), 131-142.
• 29: P. M. Lewis, R. E. Stearns, and J. Hartmanis, Memory bounds for recognition of context-free and context-sensitive languages, IEEE Conf. Rec. on Switching Circuit Th. and Logical Design (Oct. 1965), 191-202.
• 30: O. H. Ibarra, Characterizations of some tape and time complexity classes of Tm's in terms of multi-head and auxiliary stack automata, JCSS 5 (1971), 88-117.
• 31: H. B. Hunt, III, and T. G. Szymanski, manuscript in preparation.
• 32: D. J. Rosenkrantz and R. E. Stearns, Properties of deterministic top-down grammars, Inf. and Con. 17, 3 (1970), 226-256.
• 33: H. B. Hunt, III, D. J. Rosenkrantz, and T. G. Szymanski, On the equivalence, containment, and covering problems for the regular and context-free languages (submitted for publication).
• 34: J. W. Thatcher, Tree automata: an informal survey, in Currents in the Theory of Computing, A. V. Aho (ed.), Prentice-Hall, Englewood Cliffs, N. J., 1973, 143-172.
• 35: W. C. Rounds, Mappings and grammars on trees, Math. Systems Th. 4, 3 (1970), 257-287.
• 36: H. B. Hunt, III, D. J. Rosenkrantz, and T. G. Szymanski, The covering problem for linear context-free grammars, Computer Sciences Laboratory Technical Report TR 165, Dept. of Electrical Engineering, Princeton University.
• 37: R. L. Constable, H. B. Hunt, III, and S. Sahni, On the computational complexity of scheme equivalence (submitted for publication.)
• 38: D. C. Luckham, D. M. R. Park, and M. S. Paterson, On formalized computer programs, JCSS 4, 3 (1970), 220-249.
• 39: Ashok K. Chandra, Degrees of translatability and canonical forms in program schemas: Part I, Proceedings of the sixth annual ACM symposium on Theory of computing, p.1-12, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803879]
• l0: N. Jones, Preliminary report: reducibility among combinatorial problems in logn space, Proc. 7th An. Princeton Conf. on Information Sciences and Systems (March 1973), 547-551.

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.3 Complexity Measures and Classes
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Decision problems

General Terms:
Theory