|
|
 |
| Àâòîðèçàöèÿ |
|
|
|
| Ïîèñê ïî óêàçàòåëÿì |
|
|
|
|
|
|
|
 |
|
|
|
| Hopcroft J.E., Motwani R., Ullman J.D. — Introduction to Automata Theory, Languages, and Computation |
|
|
|
| Ïðåäìåòíûé óêàçàòåëü |
QBF see “Quantified boolean formula”
Quantified boolean formula 479—487
Quantifier 11 128
Quicksort 488
Quotient 146 292
Rabin, M.O. 81 511
Raghavan, P. 510
Random-number generator 469 487—489
Random-polynomial language see “ ”
Randomized Turing machine 489—492
Reachable symbol 256 258—259 298
Recursive definition 22—23
Recursive function 381
Recursive inference 173—174 184—186 190
Recursive language 327—328 373—377 474
Recursively enumerable language 326 368 379 384
Reduction 313—316 383—384
register 358
Regular expression 4—5 83—123 151 487
Regular language 180 247—248 286 289 409 “Nondeterministic “Pumping “Regular
Reversal 137—138 285 425—426
Rice's theorem 387—390
Rice, H.G. 411
Riemann's hypothesis 510
Right-linear grammar 180
Right-sentential form 178 184 189
Rightmost derivation 175—177 184
Ritchie, D. 308
Rivest, R.L. 499 511
Root 182—183
Rose, G.F. 166 304 411
RSA code 499
Rudich, S. 366
Running time see “Time complexity”
SAT see “Satisfiability problem”
Satisfiability problem 426—434 462 471
Savitch's theorem 477—478
Savitch, W.J. 511
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
Set former 32
Sethi, R. 123 217
Shamir, A. 499 511
Shamir, E. 166 304 411
Shannon switching game 487
Shannon, C.E. 81
Shifting-over 334
Shuffle, of languages 292—293
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 319 327 330 331 357
| 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 “Text search”
Structural induction 23—26
Subgraph isomorphism problem 464
SUBROUTINE 333—334
Subset construction 61—66
Substitution 282—285
Switching circuit 125
Symbol see “Generating symbol” “Input “Input “Nullable “Reachable “Stack “Start “Tape “Terminal “Useless
Symbol table 279
Syntactic category see “Variable”
tail 238
Tape 318
Tape head 318
Tape symbol 319 327 357
Tarjan, R.E. 510
Tautology problem 471
Term 209
Terminal symbol 171 176
Text search 68—72 84 111—113
Theorem 17
There exists see “Quantifier”
Thompson, K. 123
Time complexity 339—340 361—363 414 503
Token 109—111
Track 331—333
Transition diagram 48 223—224 323—326
Transition function 46 57 222 319
Transition table 48—49
Transitive Law 160
Traveling salesman problem 419—421 461—462
TREE 23—25 (see also “Parse tree”)
Treybig, L.B. 468
Trivial property 388
Truth assignment 426—427
TSP see “Traveling salesman problem”
Turing machine 307 316—329 414 473—474 for “Halting of “Las-Vegas “Monte-carlo “Multihead “Multitape “Nondeterministic “Randomized “Recursively “Two-dimensional “Universal
Turing, A.M. 1 318 323 366 411
Two-dimensional Turing machine 345
Ullman, J.D. 35 123 217 468 510
Unambiguous grammar see “Ambiguous grammar”
Undecidable problem 302 310 367—368 373—374 384 386—387 390 403—408 “Rice's “Universal
union 14 84 86 95 103 109 114—117 132 199 284 382 425—426
Unit pair 263
Unit production 256 262—266
Unit-execution-time-scheduling problem 465
Universal language 377—381
Universal Turing machine 357 377—378
UNIX regular expressions 108—110
Useless symbol 255—259
Variable 171 176
Word see “String”
World-wide-web consortium 217
XML 169 198
Yacc 194—195 208 253
Yamada, H. 123
Yield 183
Younger, D.H. 298 305
Zero-error probabilistic polynomial language see 
|
|
|
| Ðåêëàìà |
|
|
|
|
|
Î ïðîåêòå