Alternation

AHO , A.V. , HOPCROFT , J.E. , AND ULLMAN , J.D. The Design and Analysis of Computer Algorithms . Addison-Wesley , Reading, Mass ., 1974 . AHO, A.V., HOPCROFT, J.E., AND ULLMAN, J.D. The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass., 1974.

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 . 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.

BORODIN A. Personal communication. BORODIN A. Personal communication.

CHANDRA , A.K. , AND STOCKMEYER , L.J. Alternation. Proc. 17th 1EEE Symp. on Foundations of Computer Science , Houston, Texas , 1976 , pp. 98 - 108 . CHANDRA, A.K., AND STOCKMEYER, L.J. Alternation. Proc. 17th 1EEE Symp. on Foundations of Computer Science, Houston, Texas, 1976, pp. 98-108.

COOK , S.A. The complexity of theorem proving procedures . Proc. 3rd ACM Symp. on Theory of Computing , Shaker Heights, Ohio , 1971 , pp. 151 - 158 . 10.1145/800157.805047 COOK, S.A. The complexity of theorem proving procedures. Proc. 3rd ACM Symp. on Theory of Computing, Shaker Heights, Ohio, 1971, pp. 151-158. 10.1145/800157.805047

FISCHER , M.J. , AND LADNER , R.E . Propositional dynamic logic of regular programs . J. Comput. Syst. Sci. 18 , 2 ( 1979 ), 194-211. FISCHER, M.J., AND LADNER, R.E. Propositional dynamic logic of regular programs. J. Comput. Syst. Sci. 18, 2 (1979), 194-211.

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 . 10.1145/800133.804336 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. 10.1145/800133.804336

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 . 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.

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 . 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.

HOPCROFT , J.E. , AND ULLMAN , J.D. Formal Languages and their Relation to Automata . Addison- Wesley , Reading, Mass ., 1969 . HOPCROFT, J.E., AND ULLMAN, J.D. Formal Languages and their Relation to Automata. Addison- Wesley, Reading, Mass., 1969.

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 . 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.

KASA'I , T. , ADACHI , A. , AND 1WATA, S. Classes of pebble games and complete problems. SIAM J. Comput. 8 ( 1979 ), 574 - 586 . KASA'I, T., ADACHI, A., AND 1WATA, S. Classes of pebble games and complete problems. SIAM J. Comput. 8 (1979), 574-586.

KOZEN , D. On parallelism in Turing machines . Proc. 17th IEEE Symp. on Foundations of Computer Science , Houston, Texas , 1976 , pp. 89 - 97 . KOZEN, D. On parallelism in Turing machines. Proc. 17th IEEE Symp. on Foundations of Computer Science, Houston, Texas, 1976, pp. 89-97.

KOZEN , D. Complexity of Boolean algebras. Theoret. Comput. ScL I0 ( 1980 ), 221-247. KOZEN, D. Complexity of Boolean algebras. Theoret. Comput. ScL I0 (1980), 221-247.

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 . 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.

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 . 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.

PRATT , V.R. , AND STOCKMEYER , L.J . A characterization of the power of vector machines . J. Comput. Syst. ScL 12 ( 1976 ), 198 - 221 . PRATT, V.R., AND STOCKMEYER, L.J. A characterization of the power of vector machines. J. Comput. Syst. ScL 12 (1976), 198-221.

RABIN , M.O. , AND SCOTT , D . Finite automata and their decision problems . IBM J. Res. Dev. 3 ( 1959 ), 115 - 125 . RABIN, M.O., AND SCOTT, D. Finite automata and their decision problems. IBM J. Res. Dev. 3 (1959), 115-125.

Rozzo, W. L. General context-free language recognition. Ph.D. Diss ., Computer Science Division, Univ. of California , Berkeley, Calif ., 1978 . Rozzo, W.L. General context-free language recognition. Ph.D. Diss., Computer Science Division, Univ. of California, Berkeley, Calif., 1978.

SAVITCH , W.J . Relationships between nondeterministic and deterministic tape complexities . J. Comput. Syst. Sci 4 ( 1970 ), 177 - 192 . SAVITCH, W.J. Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci 4 (1970), 177-192.

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 . 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.

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 . 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.

SIMON , J. On feasible numbers . Proc. 9th ACM Symp. on Theory of Computing, Boulder, Colo. , 1977 , pp. 195 - 207 . 10.1145/800105.803409 SIMON, J. On feasible numbers. Proc. 9th ACM Symp. on Theory of Computing, Boulder, Colo., 1977, pp. 195-207. 10.1145/800105.803409

STOCKMEYER , L.J . The polynomial-time hierarchy . Theoret. Comput. ScL 3 ( 1977 ), 1 - 22 . STOCKMEYER, L.J. The polynomial-time hierarchy. Theoret. Comput. ScL 3 (1977), 1-22.

STOCKMEYER , L.J. , AND CHANDRA , A.K . Provably difficult combinatorial games . SIAM J. Comput. 8 ( 1979 ), 151 - 174 . STOCKMEYER, L.J., AND CHANDRA, A.K. Provably difficult combinatorial games. SIAM J. Comput. 8 (1979), 151-174.

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 . 10.1145/800125.804029 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. 10.1145/800125.804029

WRATHALL , C . Complete sets and the polynomial-time hierarchy . Theoret. Comput. ScL 3 ( 1977 ), 23 - 34 . WRATHALL, C. Complete sets and the polynomial-time hierarchy. Theoret. Comput. ScL 3 (1977), 23-34.