Dichotomization, reachability, and the forbidden subgraph problem(Extended Abstract)

ABSTRACT

We present several techniques for proving lower bounds that can be applied to problems about grammars, formal languages, program schemes, simple programming languages, and automata. These techniques include dichotomization, extensions of dichotomization to certain classes of relational problems, recursive analogues of the Post Correspondence Problem, and the reachability problem. These techniques provide many new lower bounds and provide a unified framework for viewing much of the work on the complexity of problems about grammars, languages, schemes, and automata. We show how to prove the undecidability of a problem by efficiently reducing the membership problem for Tms that always halt to it. We also introduce the forbidden subgraph problem.

REFERENCES

• 1: Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
• 2: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 3: D.C. Luckham, D.M.R. Park, and M.S. Paterson, On formalized computer programs, JCSS 4 (1970), 220-249.
• 4: H. B. Hunt, III , T. G. Szymanski, On the complexity of grammar and related problems, Proceedings of seventh annual ACM symposium on Theory of computing, p.54-65, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803753]
• 5: H. B. Hunt, III, A complexity theory of grammar problems, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.12-18, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811536]
• 6: R.L. Constable, H.B. Hunt, III, and S. Sahni, On the computational complexity of scheme equivalence, TR 74-201, Dept. of Computer Science, Cornell University, Ithaca, New York.
• 7: H.B. Hunt, III, On the complexity of finite, pushdown, and stack automata, to appear in Math. Systems Th.
• 8: Neil D. Jones , Steven S. Muchnick, Even simple programs are hard to analyze, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.106-118, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512988]
• 9: R.E. Miller, Some undecidability results for parallel program schemata, SIAM J. Computing 1 (1972), 119-129.
• 10: D. Tsichritzis, The Equivalence Problem of Simple Programs, Journal of the ACM (JACM), v.17 n.4, p.729-738, Oct. 1970 [doi>10.1145/321607.321621]
• 11: Z. Manna, Program schemas, in Currents in the Theory of Computing, edited by A.V. Aho, Prentice-Hall, Englewood Cliffs, N.J., 1973, 90-142.
• 12: S.R. Kosaraju, Analysis of structured programs, JCSS 9 (1974), 232-255.
• 13: M.S. Hecht and J.D. Ullman, Flow graph reducibility, SIAM J. on Computing 1 (1972), 188-202.
• 14: Thomas Gregory Szymanski, Generalized bottom-up parsing., 1973
• 15: T.G. Szymanski and J.H. Williams, Non-canonical extensions of bottom-up parsing techniques, to appear in SIAM J. on Computing.
• 16: K. Culik and R. Cohen, LR-regular grammars—an extension of LR(k) grammars, JCSS 7 (1973), 66-96.
• 17: Eberhard Bertsch, A Decidability Result for Sequential Grammars, Proceedings of the 2nd Colloquium on Automata, Languages and Programming, p.577-583, July 29-August 02, 1974
• 18: Charles Nicholas Fischer, On parsing context free languages in parallel environments., 1975
• 19: J.L. Kelley, General Topology, Van Nostrand, New York, 1955.
• 20: S.J. Garland and D.C. Luckham, Program schemes, recursion schemes, and formal languages, JCSS 7 (1973), 119-160.
• 21: Bruce P. Lester, Program schemas with concurrency: execution time and hangups, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.185-193, January 20-22, 1975, Palo Alto, California [doi>10.1145/512976.512995]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Theory