Comparative schematology and pebbling with auxiliary pushdowns (Preliminary Version)

ABSTRACT

This paper has three claims to interest. First, it combines comparative schematology with complexity theory. This combination is capable of distinguishing among Strong's “languages of maximal power,” a distinction not possible when comparative schematology is based on computability considerations alone, and it is capable of establishing exponential disparities in running times, a capability not currently possessed by complexity theory alone. Secondly, this paper inaugurates the study of pebbling with auxiliary pushdowns, which bears to plain pebbling the same relationship as Cook's study of space-bounded machines with auxiliary pushdowns bears to plain space-bounded machines. This extension of pebbling serves as the key to the problems of comparative schematology mentioned above. Finally, this paper advantageously displays the virtues of recent work by Gabber and Galil giving explicit constructions for certain graphs, for the availability of such explicit constructions is essential to the results of this paper.

REFERENCES

• 1: 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]
• 2: O. Gabber and Z. Galil, Explicit Constructions of Linear Size Superconcentrators, 20th Ann. ACM Symp. on Foundations of Computer Science, 29-31 October 1979, San Juan, PR.
• 3: John Hopcroft , Wolfgang Paul , Leslie Valiant, On Time Versus Space, Journal of the ACM (JACM), v.24 n.2, p.332-337, April 1977 [doi>10.1145/322003.322015]
• 4: Thomas Lengauer , Robert Endre Tarjan, Upper and lower bounds on time-space tradeoffs, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.262-277, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804420]
• 5: M. S. Paterson and C. E. Hewitt, Comparative Schematology, Proj. MAC Conf. on Concurrent Systems and Parallel Computation, 2-5 June 1970, Woods Hole, MA.
• 6: W. J. Paul, R. E. Tarjan and J. R. Celoni, Space Bounds for a Game on Graphs, Math. Sys. Theory, 10 (1977) 239–251.
• 7: N. Pippenger, Fast Simulation of Combinational Logic Networks by Machines without Random-Access Storage, 15th Ann. Allerton Conf. on Communication, Control, and Computing, 28-30 September 1977, Monticello, IL.
• 8: Lawrence Snyder, An analysis of parameter evaluation for recursive-procedures., 1973
• 9: H. R. Strong, High Level Languages of Maximum Power, 12th Ann. Symp. on Switching and Automata Theory, 13-15 October 1971, East Lansing, MI.

INDEX TERMS

Primary 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)

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.3 Tradeoffs among Complexity Measures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.0 General
      G.2.2 Graph Theory

General Terms:
Theory