Lex 110-111, 123 Lexical analyzer 2, 84, 109-111 Linear integer programming problem 465 Literal 436 LR(fc) grammar 253

Markup language

See HTML, XML Max, of a language 147, 292 McCarthy, J. 81 McCulloch, W. S. 81 McNaughton, R. 123, 167 Mealy, G. H. 81 Membership test 153, 298-301 Miller, G. L. 510 Min, of a language 147, 292 Minimization, of DFAs 159-164 Minimum-weight spanning tree 415-416

Minsky, M. L. 366, 411 Modified Posts correspondence problem 394-402 Modular- arithmetic 501-503 Modus ponens 7 Monte-carlo Turing machine 493 Moore, R F. 81, 167 Moores law 1 Motwani, R. 510 Move

See Transition function Multihead Turing machine 344 Multiple tracks

See Track Multiplication 362, 501-503 Multistack machine

See Sta<;k machine Multitape Turing machine 336-340 Mutual induction 26-28

Natural language 191 Naur, R 217

See Node-cover problem

See Nondeterministic finite automaton Node-cover problem 452-453, 462 Nondeterministic finite automaton 55-70, 96, 150-151, 163

See also e-NFA Nondetermmistic polynomial space

See AfVS Nondetermmistic polynomial time

SeeAfV

Nondeterministic Turing machine 340-342, 473, 476-478, 493 See also MV, NVS

Nonrecursive language

See Undecidable problem

Nonrecursively enumerable language See Recursively enumerable language

Nonterminal

See Variable

Normal form 255-273

Ar 419, 423, 426, 470, 479, 497-498, 505-508

NP-complete problem 422 424,447, 450, 470-472 See also CUque problem. Coloring problem, CSAT, Dominating-set problem. Edge-cover problem, Exact-cover problem, Firehouse problem, Hamilton-circuit problem, Hamilton-path problem. Independent-set problem. Knapsack problem. Linear integer programming problem, Node-cover problem. Satisfiability problem. Subgraph isomorphism problem, 3SAT, Traveling salesman problem. Unit-execution-time-scheduling problem

NP-hard problem 423

See also Intractable problem AfVS 473, 477-478 Nullable symbol 259-260, 298

Observation 17 Oettinger, A. G. 253 Ogden, W. 304 Ogdens lemma 281

V 414, 423, 425-426, 479, 497 Palindrome 170, 177-178 Papadimitriou, C. H. 510 Parent 182

Parse tree 181-189, 207, 274-275

See also Ttee Parser 169, 192-195 Partial function 329 Partial solution, to PCP 395 Partial-removal operation 147, 292 Partition 161 Paull, M. C. 304 PCP

See Posts correspondence problem

See Pushdown automaton Perles, M. 166, 304, 411 Permutation, of a language 293 Pigeonhole principle 66 Pitts, W. 81

Polynomial space 469, 473-478

See also VS Polynomial time 5

See also V, UV, ZW Polynomial-time reduction 413-414, 421-423, 478-479

Pop 220

Post, E. 366,411

Posts correspondence problem 392-402

Pratt, V. R. 510

Precedence, of operators 88-89, 208

Prefix property 248-249

Prime number 470, 498-508

Problem 31-33, 417

Product construction 134

Production 171

See also e-production, Unit production

Proof 5-6,12

See also Contradiction, proof by. Deductive proof, If-and-only-if proof. Inductive proof

Property, of langnages 387-388

Protocol 2, 395

VS 469, 473, 477-479

PS-complete problem 478-479

See also Quantified boolean formula. Shannon switching game

Public-key signature 500-501 Pumping lemma 126-130, 274-281 Push 220

Pushdown automaton 219-246,294-295

See also Deterministic pushdown automaton. Stack machine

See Quantified boolean formula Quantified boolean formula 479-487 Quantifier 11, 128 Quicksort 488 Quotient 146, 292

Rabin, M. 0. 81, 511 Raghavan, P. 510

Randomized Turing machine 489-492

Random-number generator 469, 487-489

Random-polynomial language See nV

Reachable symbol 25C, 258-259,298 Recursive definition 22-23 Recursive function 381 Recursive inference 173-174, 184-

186, 190-191 Recursive language 327-328. 373-

377, 474

Recursively enumerable language 326, 368 379, 384

Reduction 313-316, 383-384

See also Polynomial-time reduction

Register 358

Regular expression 4-5, 83-123.151. 487

Regular language 180, 247-248, 286, 289, 409 See also Deterministic finite automaton, Nondeterministic finite automaton. Pumping lemma, Regular expression

Reversal 137-138, 285, 425-426

Rice, H. G. 411

Rices theorem 387-390

Riemanns hypothesis 510

Right-linear grammar 180

Rightmost derivation 175-177, 184

Right-sentential form 178, 184, 189

Ritchie, D. 308

Rivest, R. L. 499, 511

Root 182-183

Rose, G. F. 166, 304, 411

KT 469-470, 488, 492-498, 504

RSA code 499

Rudich, S. 366

Running time

See Time complexity

See Satisfiability problem Satisfiability problem 426-434, 462, 471

Savitch, \V. .1. 511 Savitchs theorem 477-478

Scheduling problem

See Unit-execution-time-scheduling problem Scheinberg, S. 305 Schutzenberger, M. P. 253, 411 Scott, D. 81 Seiferas, J. I. 167 Semi-infinite tape 345-348 Sentential form 178

See also Left-sentential form. Right-sentential form Set former 32 Sethi, R. 123, 217 Shamir, A. 499, 511 Shamir, E. 166, 304, 411 Shannon, C. E. 81 Shannon switcliing game 487 Shifting-over 334 Shuffle, of languages 292-293

See Input symbol Size, of inputs 417 Spanier, E. H. 166 Spanning tree 415

See also Minimum-weight spanning tree Stack 219-220, 476 Stack machine 348-351 Stack symbol 222, 227 Star 86

See also Closure Start state 46, 57, 222, 319 Start symbol 171, 222 State 2-3, 39, 46, 57, 221, 227, 3l9, 327, 330 331, 357

See also Dead state State elimination 96-101 Stearns, R. E. 167, 366, 468, 510 Stockmeyer, L. J. 510 Storage device 355-356 String 29-30, 49, 176, 369 String search

See Tex-t. search Structural induction 23-26 Subgraph isomorphism problem 464