Hopcroft J.E., Motwani R., Ullman J.D. — Introduction to Automata Theory, Languages, and Computation :: Электронная библиотека попечительского совета мехмата МГУ

Главная Ex Libris Книги Журналы Статьи Серии Каталог Wanted Загрузка ХудЛит Справка Поиск по индексам Поиск Форум

Авторизация

Поиск по указателям

Hopcroft J.E., Motwani R., Ullman J.D. — Introduction to Automata Theory, Languages, and Computation

Обсудите книгу на научном форуме

Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter

Название: Introduction to Automata Theory, Languages, and Computation

Авторы: Hopcroft J.E., Motwani R., Ullman J.D.

Аннотация:

This book is a rigorous exposition of formal languages and models of computation, with an introduction to computational complexity. The authors present the theory in a concise and straightforward manner, with an eye out for the practical applications. Exercises at the end of each chapter, including some that have been solved, help readers confirm and enhance their understanding of the material. This book is appropriate for upper-level computer science undergraduates who are comfortable with mathematical arguments.

Язык:

Рубрика: Computer science/Алгоритмы/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Издание: second edition

Год издания: 2001

Количество страниц: 521

Добавлена в каталог: 18.11.2005

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

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 “ $\mathcal{RP}$ ”
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 $\mathcal{ZPP}$

1 2

О проекте