Tree-size bounded alternation(Extended Abstract)

ABSTRACT

The size of an accepting computation tree of an alternating Turing machine (ATM) is introduced as a complexity measure. Tree-size on ATM's is shown to closely correspond to time on nondeterministic TM's and on nondeterministic auxiliary pushdown automata. The later gives a useful new characterization of the class of languages log-space-reducible to context-free languages. Relationships with parallel-time complexity are also explored. ATM computations using at most space S(n) and tree-size Z(n) (simultaneously) can be simulated in alternating time S(n).log Z(n). Several well-known simulations, e.g., Savitch's theorem, are special cases of this result. It also leads to improved parallel-time bounds for many problems, e.g., context-free language recognition in time 0(log2n) on several parallel models.

REFERENCES

• 1: Berman, L., "Precise Bounds for Presberger arithmetic and the reals with addition," Conf. Rec. IEEE 18th Symp. on the Foundations of Computer Science (1977) 95-99.
• 2: Borodin, A. "On relating time and space to size and depth," SIAM J. Comput. 6, 4(1977) 733-743.
• 3: Stephen A. Cook, Path systems and language recognition, Proceedings of the second annual ACM symposium on Theory of computing, p.70-72, May 04-06, 1970, Northampton, Massachusetts, United States [doi>10.1145/800161.805151]
• 4: 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]
• 5: Chandra, A.K. and L.J. Stockmeyer. "Alternation," Conference Record IEEE 17th Annual Symposium on Foundations of Computer Science (1976) 98-108.
• 6: Chandra, A.K., D. Kozen, and L.J. Stockmeyer. "Alternation," to appear.
• 7: Erni, W. "Some further languages log-tape reducible to context-free languages," Institut fur Angewandte Informatik und Formale Beschreibungverfahren, Universitat Karlsruhe, W. Germany.
• 8: Michael J. Fischer , Richard E. Ladner, Propositional modal logic of programs, Proceedings of the ninth annual ACM symposium on Theory of computing, p.286-294, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803418]
• 9: Kozen, D. "On parallelism in Turing machines," Conference Record IEEE 17th Annual Symposium on Foundations of Computer Science (1976) 89-97.
• 10: Ladner, R.E., R.J. Lipton, and L.J. Stockmeyer. "Alternating pushdown automata," Proc. 19th IEEE Symposium on Foundations of Computer Science (1978) 92-106.
• 11: Lewis, P.M., R.E. Stearns and J. Hartmanis, "Memory bounds for recognition of context-free and context sensitive languages," Conference Record IEEE 6th Annual Symposium on Switching Circuit Theory and Logic Design (1965) 191-202.
• 12: Monien, B. "Relationships between pushdown automata and tape-bounded Turing machines," in Automata, Languages, and Programming, M. Nivat (ed.), American Elsevier, NY (1972) 575-583.
• 13: Vaughan R. Pratt , Michael O. Rabin , Larry J. Stockmeyer, A characterization of the power of vector machines, Proceedings of the sixth annual ACM symposium on Theory of computing, p.122-134, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803892]
• 14: Pratt, V.R. and L.J. Stockmeyer. "A characterization of the power of vector machines," JCSS 12 2(1976) 198-221.
• 15: Walter Lawrence Ruzzo, General context-free language recognition., 1978
• 16: Ruzzo, W.L. "An improved characterization of the power of vector machines," University of Washington Computer Science Department Technical Report 78-10-01.
• 17: Savitch, W.J. "Relationships between nondeterministic and deterministic tape complexities," Journal of Computer and System Sciences 4:2 (Apr 1970) 177-192.
• 18: 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]
• 19: Sudborough, I.H. "Time and tape bounded auxiliary pushdown automata," in Mathematical Foundations of Computer Science, Springer Verlag Lecture Notes in Computer Science, v. 53 (1977) 493-503.
• 20: I. H. Sudborough, On the Tape Complexity of Deterministic Context-Free Languages, Journal of the ACM (JACM), v.25 n.3, p.405-414, July 1978 [doi>10.1145/322077.322083]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Alternation and nondeterminism

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)
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems

General Terms:
Algorithms, Languages, Theory