Ashok K. Chandra
- 1 AHO, A.V., HOPCROFT, J.E., AND ULLMAN, J.D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974. Google Scholar
- 2 HERMAN, L. Precise bounds for Presburger arithmetic and the reals with addition. Proc. 18th IEEE Symp. on Foundations of Computer Science, Providence, R.I., 1977, pp. 95-99.Google Scholar
- 3 BORODIN, A. Personal communication.Google Scholar
- 4 CHANDRA, A.K., AND STOCKMEYER, L.J. Alternation. Proc. 17th 1EEE Symp. on Foundations of Computer Science, Houston, Texas, 1976, pp. 98-108.Google Scholar
- 5 COOK, S.A. The complexity of theorem proving procedures. Proc. 3rd ACM Symp. on Theory of Computing, Shaker Heights, Ohio, 1971, pp. 151-158. Google Scholar
- 6 FISCHER, M.J., AND LADNER, R.E. Propositional dynamic logic of regular programs. J. Comput. Syst. Sci. 18, 2 (1979), 194-211.Google Scholar
- 7 GOLDSCHLAGER, L.M. A unified approach to models of synchronous parallel machines. Proc. 10th ACM Symp. on Theory of Computing, San Diego, Calif. 1978, pp. 89-94. Google Scholar
- 8 HARTMANIS, J., AND HUNT, H.B. III. The LBA problem and its importance in the theory of computing. In Complexity of Computation, R.M. Karp, Ed., American Mathematical Society, Providence, R.I., 1974, pp. 1-26.Google Scholar
- 9 HARTMANIS, J., AND SIMON, J. On the power of multiplication in random access machines. Proc. 15th IEEE Symp. on Switching and Automata Theory, New Orleans, La., 1974, pp. 13-23.Google Scholar
- 10 HOPCROFT, J.E., AND ULLMAN, J.D. Formal Languages and their Relation to Automata. Addison- Wesley, Reading, Mass., 1969. Google Scholar
- 11 KARP, R.M. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds., Plenum Press, New York, 1972, pp. 85-104.Google Scholar
- 12 KASA'I, T., ADACHI, A., AND 1WATA, S. Classes of pebble games and complete problems. SIAM J. Comput. 8 (1979), 574-586.Google Scholar
- 13 KOZEN, D. On parallelism in Turing machines. Proc. 17th IEEE Symp. on Foundations of Computer Science, Houston, Texas, 1976, pp. 89-97.Google Scholar
- 14 KOZEN, D. Complexity of Boolean algebras. Theoret. Comput. ScL I0 (1980), 221-247.Google Scholar
- 15 LADNER, R.E., LIPTON, R.J., AND STOCKMEYER, L.J. Alternating pushdown automata. Proc. 19th 1EEE Symp. on Foundations of Computer Science, Ann Arbor, Mich., 1978.Google Scholar
- 16 MEYER, A.R., AND FISCHER, M.J. Economy of description of automata, grammars, and formal systems. Proc. 12th IEEE Symp. on Switching and Automata Theory, East Lansing, Mich., 1971, pp. 188-191.Google Scholar
- 17 PRATT, V.R., AND STOCKMEYER, L.J. A characterization of the power of vector machines. J. Comput. Syst. ScL 12 (1976), 198-221.Google Scholar
- 18 RABIN, M.O., AND SCOTT, D. Finite automata and their decision problems. IBM J. Res. Dev. 3 (1959), 115-125.Google Scholar
- 19 Rozzo, W.L. General context-free language recognition. Ph.D. Diss., Computer Science Division, Univ. of California, Berkeley, Calif., 1978. Google Scholar
- 20 SAVITCH, W.J. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci 4 (1970), 177-192.Google Scholar
- 21 SAVITCH, W.J., AND STIMSON, M.J. The complexity of time bounded recursive computations. Proc. 1976 Johns Hopkins Conf. on Information Sciences and Systems, Baltimore, Md., pp. 42-46.Google Scholar
- 22 SCOTT, D. Outline of a mathematical theory of computation. Proc. 4th Ann. Princeton Conf. on Information Sciences and Systems, Princeton, N. J. 1970, pp. 169-176.Google Scholar
- 23 SIMON, J. On feasible numbers. Proc. 9th ACM Symp. on Theory of Computing, Boulder, Colo., 1977, pp. 195-207. Google Scholar
- 24 STOCKMEYER, L.J. The polynomial-time hierarchy. Theoret. Comput. ScL 3 (1977), 1-22.Google Scholar
- 25 STOCKMEYER, L.J., AND CHANDRA, A.K. Provably difficult combinatorial games. SIAM J. Comput. 8 (1979), 151-174.Google Scholar
- 26 STOCKMEYER, L.J., AND MEYER, A.R. Word problems requiring exponentialtime: Preliminary report. Proc. 5th ACM Symp. on Theory of Computing, Austin, Texas, 1973, pp. 1-9. Google Scholar
- 27 WRATHALL, C. Complete sets and the polynomial-time hierarchy. Theoret. Comput. ScL 3 (1977), 23-34.Google Scholar
Index Terms
- Alternation
Recommendations
From bidirectionality to alternation
We describe an explicit simulation of 2-way nondeterministic automata by 1-way alternating automata with quadratic blow-up. We first describe the construction for automata on finite words, and extend it to automata on infinite words.
Alternation
SFCS '76: Proceedings of the 17th Annual Symposium on Foundations of Computer ScienceWe define alternating Turing Machines which are like nondeterministic Turing Machines, except that existential and universal quantifiers alternate. Alternation links up time and space complexities rather well, in that alternating polynomial time equals ...
Alternation for sublogarithmic space-bounded alternating pushdown automata
This paper investigates infinite hierarchies on alternation-depth and alternation-size of alternating pushdown automata (apda's) with sublogarithmic space. We first show that there is an infinite hierarchy on alternation-depth for apda's with ...
Comments