11.7 References for Chapter 11

Paper [2] initiated the study of classes of languages defined by bounds on the amount of space used by a Turing machine. The first PS-complete problems were given by Karp [4] in his paper that explored the importance of NP-completeness. The PS-completeness of the problem of Exercise 11.3.2 - whether a regular expression is equivalent to E* - is from there.

PS-completeness of quantified boolean formulas is unpublished work of L. J. Stockmeyer. PS-completeness of the Shannon switchmg game (Exercise 11.3.3) is from [1].

The fact that the primes are in MV is by Pratt [9]. The presence of the composite numbers in TIV was first shown by Rabin [10]. Interestingly, there w is published at about the same time a proof that the primes are actually in V, provided that an unproved, but generally believed, assmnption called the extended Riemann hypothesis is true [6].

Several books are available to extend your knowledge of the topics introduced in this chapter. [7] covers randomized algorithms, including the complete algorithms for primalitj testing. [5] is a source for the algorithms of modular arithmetic. [3] and [8] treat a number of other complexity classes not mentioned hero.

1. S. Even and R. E. Tarjan, A combinatorial problem which is complete for polynomial space, J. ACM 23:4 (1976), pp. 710-719.

2. J. Hartmanis, P. M. Lewis II, and R. E. Stearns, Hierarchies of memory limited computations, Proc. Sixth Annual IEEE Symposium on Switching Circuit Theory and Logical Design (1965), pp. 179-190.

3. J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addis on-Wesley, Reading MA, 1979.

4. R. M. Karp, Reducibility among combinatorial problems, in Complexity of Computer Computations (R. E. Miller, ed.), Pleimm Press, New York, 1972, pp. 85-104.

5. D. E. Knuth, The Art of Computer Programming, Vol II: Seminumerical Algorithms, Addison-Wesley, Reading MA, 1997 (third edition).

6. G. L, Miller, Riemanns hypothesis and tests for primality, J. Computer and System Sciences 13 (1976), pp. 300-317.

7. R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge Univ. Press, 1995.

8. C. H. Papadimitriou, Computational Complexity, Addison-Wesley, Reading М.Д., 1994.

9. V. R. Pratt, Every prime has a succinct certificate, SIAM J. Computing 4:3 (1975), pp. 214-220.

11.7. REFERENCES FOR CHAPTER 11 511

10. M. O, Rabin, Probabilistic algorithms, in Algorithms and Complexity: Recent Results and New Directions (J. F. Traub, ed.), pp. 21-39, Academic Press, New York, 1976.

11. R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM 21 (1978), pp. 120-126.

12. W. J. Savitch, Relationships between deterministic and nondeterministic tape complexities, J. Computer and System Sciences 4:2 (1970), pp. 177-192.

Index

Acceptance by empty stack 230-235, 249-250

Acceptance by final state 229-235,

249-250 Accepting state 46, 57, 222, 319 Accessible state 45 Ackermanns function 381 Address, of memory 357-358 Adelman, L. 499, 511 Aho, A. V. 35, 123, 217 Algebra 85-86, 114-120 Algorithm

See Recursive language Alphabet 28-29, 132 Alphabetic character 109 Alphanumeric character 109 Ait, of languages 147, 292 Ambiguous grannnar 205-212, 249-

251, 302, 40406 Ancestor 182 Annihilator 95, 115 Arithmetic expression 23-26, 208-

Associative law 114-115

Automaton 26-28

See also Counter machine. Deterministic finite automaton. Finite automaton. Non-deterministic finite automaton, Pushdown automaton. Stack machine, Turing machine

Backus, J. W. 217

Balanced parentheses 192-193

Bar-Hillel, Y. 166, 304, 411

Basis 19, 22-23

Blank 318-319, 346

Block, of a partition 161

Body 171

Boolean expression 426-428, 436 See also Quantified boolean formula Borosh, I. I. 468 Bottom-of-stack marker 351

Cantor, D. C. 217, 411 CFG

See Context-free grammar

See Context-free language Character class 108 Child 182

Chomsky, N. 1, 191, 217, 266, 411 Chomsky normal form 266-269, 295-296

Church, A. 318, 366 Church-Turing thesis 318 Clause 436

Clique problem 462, 465 Closure 85, 87, 104, 109, 117, 199, 284, 382, 425-426 See also e-closure Closure property 131

See also Alt, of languages. Closure, Complementation, Con-