Ãëàâíàÿ    Ex Libris    Êíèãè    Æóðíàëû    Ñòàòüè    Ñåðèè    Êàòàëîã    Wanted    Çàãðóçêà    ÕóäËèò    Ñïðàâêà    Ïîèñê ïî èíäåêñàì    Ïîèñê    Ôîðóì   
blank
Àâòîðèçàöèÿ

       
blank
Ïîèñê ïî óêàçàòåëÿì

blank
blank
blank
Êðàñîòà
blank
Hopcroft J.E., Ullman J.D. — Introduction to automata theory, languages, and computation
Hopcroft J.E., Ullman J.D. — Introduction to automata theory, languages, and computation



Îáñóäèòå êíèãó íà íàó÷íîì ôîðóìå



Íàøëè îïå÷àòêó?
Âûäåëèòå åå ìûøêîé è íàæìèòå Ctrl+Enter


Íàçâàíèå: Introduction to automata theory, languages, and computation

Àâòîðû: Hopcroft J.E., Ullman J.D.

Àííîòàöèÿ:

It has been more than 20 years since this classic book on formal languages, automata theory, and computational complexity was first published. With this long-awaited revision, the authors continue to present the theory in a concise and straightforward manner, now with an eye out for the practical applications. They have revised this book to make it more accessible to today's students, including the addition of more material on writing proofs, more figures and pictures to convey ideas, side-boxes to highlight other interesting material, and a less formal writing style. Exercises at the end of each chapter, including some new, easier exercises, help readers confirm and enhance their understanding of the material.


ßçûê: en

Ðóáðèêà: Ìàòåìàòèêà/

Ñòàòóñ ïðåäìåòíîãî óêàçàòåëÿ: Ãîòîâ óêàçàòåëü ñ íîìåðàìè ñòðàíèö

ed2k: ed2k stats

Ãîä èçäàíèÿ: 1979

Êîëè÷åñòâî ñòðàíèö: 426

Äîáàâëåíà â êàòàëîã: 15.12.2013

Îïåðàöèè: Ïîëîæèòü íà ïîëêó | Ñêîïèðîâàòü ññûëêó äëÿ ôîðóìà | Ñêîïèðîâàòü ID
blank
Ïðåäìåòíûé óêàçàòåëü
Many-one reduction      212
MAX      72 142 244—245 281
McCarthy, J.      54
McCreight, E. M.      319
McCulloch, W. S.      54
McNaughton, R.      54 76
Mealy machine      42—45
Mealy, G. H.      54
Membership problem      139—141 281
Metalinear language      143
Meyer, A. R.      124 176 319 375—376
Millen, J. K.      54
Miller, G. L.      232 375
MIN.      72 142 244—245 279 281
Minimization of finite automata      67—71
Minsky, M. L.      54 76 176 216
Modified PCP      195—196
Monma, C. L.      374
Moore machine      42—45
Moore, E. F.      54 76 284
Morris. J. H.. Jr      54
Move      149
Multidimensional Turing machine      164—165
Multihead Turing machine      165
Multitape Turing machine      161—163
My hill, J.      76 232
Myhill — Nerode theorem      65—67
Naur. P.      106
Nerode, A.      76 (see also Myhill — Nerode theorem)
Neuron net      47
Next move function      148
NFA      see Nondeterministic finite automaton
Node      see Vertex
Nondeterministic finite automaton      19—33
Nondeterministic space complexity      288 300—305
Nondeterministic space hierarchy      304—305
Nondeterministic time complexity      288 300 354—362
Nondeterministic time hierarchy      306
Nondeterministic Turing machine      163—164 288
Nonerasing stack automaton      382 385—387 393
Nonterminal      see Variable
Normal form PDA      234
NP-complete problem      324—343
NP-hard problem      324
NSPACE      see Nondeterministic space complexity
NTime      see Nondeterministic time complexity
Number theory      354 371
Oettinger, A. G.      123
Off-line Turing machine      166 174 285—286
Ogden, W.      145 394
Ogden’s lemma      129—130
One-way stack automaton      382 389 393
Operator grammar      105
Oppen. D. C.      375
Oracle      209—213 362—365 371
Output alphabet      42—43 272
Output tape      167
P-complete problem      347—349
Pair generator      169
Palindrome      2 11—12 105
Papadimitriou, C. H.      374
Papert, S.      76
Parikh. R. J.      145
Parse tree      see Derivation tree
Parser      9 268
Partial recursive function      151
Partial solution to PCP      197
Partition problem      341
Paul, W. J.      319
Pauli, M. C.      106
PCP      see Post's correspondence problem
PDA      see Pushdown automaton
Perfect squares      57
Perles. M.      76 145 216
Phrase structure grammar      see Type 0 grammar
Pippenger, N.      319
Pitts, W.      54
Polynomial time reduction      322
pop      235 382
Porter. J. H.      46 54
Positive closure      28 230—231 278 280
Post tag system      213
Post's correspondence problem      193—201
Post, E.      176 216
Power set      5
Pratt. V. R.      54 375—376
Predecessor      2
Predicting machine      240—243
Prefix      1
prefix property      121 260
Prenex normal form      355
Presberger arithmetic      354 371
PRIMES      57—58 342—343
Primitive recursive function      175
Principal AFL      283
Problem      177
Production      77—79
Proper prefix/suffix, I Proper subtraction      151
Property, of languages      188
PSPACE      321
PSPACE-complete problem      324 343—347
PSPACE-hard problem      324
Pumping lemma      55—58 72 125—128 143 394-395
push      235 381
Pushdown automaton      9 107—124 264
Pushdown transducer      124
Quantified boolean formula      343—346
Quotient      62—63 142 244 276—277 280 392
Rabin, M. O.      54 319 375
Rackoff, C.      375
RAM      see Random access machine
Random access machine      166—167
RANGE      6
Reachability problem      349—350
Reals with addition      354—362
Reckhow, R. A.      176
Recursion theorem      208
Recursive function      175 207—209
Recursive language      151 169—170 179 181 210 227—228 270-271
Recursively enumerable language      150 168—169 180—192 210 228 230 270
Reduction      321—324 212—213
Reedy, A.      216
Refinement, of an equivalence relation      65
Reflexive and transitive closure      8
Reflexivity      7
Regular expression      9 28—35 51 350—353 370
Regular grammar      217—220
Regular set      18 55—76 142 189 203 205 218 228 246 270—271 277—278 280-281
Relation      6—8
Reversal      71—72 142 281
Rice, H. G.      106 145 216
Rice’s theorem      185—192
Right sentential form      249
Right-linear grammar      see Regular grammar
Right-matching      39
Rightmost derivation      87
Ritchie, R. W.      319
Rogers, H., Jr      176
Root      3
Rose, G. F.      76 124 145 216 284
Rosenberg, A. L.      124 176
Rosenkrantz, D. J.      106 216 269 374—376 395
Ross, D. T.      46 54
Rozenberg, G.      395
Ruby, S.      319
Ruzzo, W. L.      145
Sa      see Stack automaton
Sahni, S.      375
Salomaa, A.      106 395
Satisfiability problem      325—331 370
Savitch's theorem      301—302
Savitch, W. J.      216 319 375
Scattered-context grammar/language      282—283
Schaefer, T. J.      374 376
Scheduling problem      367
Scheinberg, S.      145
Schutzenberger, M. P.      106 123 216 267
Scott, D.      54
Seiferas. J. L      76 176 319
Self-embedding grammar      229
Selman, A.      376
Semi — Thue system      see Type 0 grammar
Semilinear set      72
Sentential form      81 143 389 395
Set      5—6
Set former      5
Sethi, R.      374—375
Shamir, E.      76 145 216
Shank, H.      145
Shannon switching game      370 372—374
Shannon, C. E.      54 176
Shepherdson, J. C.      54
Shifting over symbols      156—157
Shuffle      142
Sieveking, M.      374
Simple grammar      229
Simulation      364
Singletary, W. E.      216
Singleton      192
Solovay, R.      375—376
Son      4
Space complexity      285—289 295—298 300—319 343—353 384—385 387-388 393
Space constructibility      297
Space hierarchy      297—298
Space-bounded Turing machine      285
Spanier. E. H.      76 145
Spanning-tree problem      367
Speed-up      see Blum’s speed-up theorem Linear
Springsteel, F. N.      375
STACK      107 378 389
Stack alphabet      110
Stack automaton      381—389 393
Stanley, R. J.      145
Start state      148 (see also Initial state)
Start symbol      110
State      17 110 148 272 377
Stearns, R. E.      76 106 124 176 247 267 269 319 375
Steiglitz, K.      374
Stockmeyer, L. J.      375—376
Storage in finite control      153 154
Strassen, V.      375
String      1
Strong connectivity problem      370
sub      282
SUBROUTINE      157—158
Substitution      60—61 131—132 230—231 277—278 280—281 283
Successor      2
Sudborough, I. H.      375
Suffix      1
Suzuki, N.      375
Switching circuit      13 47
Symbol      1
Symmetry      7
Syntactic category      see Variable
Szymanski, T. G.      374 376
Taniguchi, K.      269
Tape      17 36 148 378
Tape alphabet      173
Tape compression      288—289
Tape head      36
Tape reduction      289 292—295
Tape symbol      148
Tarjan, R. E.      319 374—375
Terminal, of a grammar      77 79 389
Text editor      46
Thompson, K.      46 54
Three-satisfiability      330—331
Time complexity      286—295 299—300 307 313 320—343 378—381 393
Time constructibility      299
Time hierarchy      295 299 303
Time-bounded Turing machine      286
Torii, K.      145
Total recursive function      151
Track, of a tape      154
Trakhtenbrot. B. A.      319
Transition diagram      16
Transition function      17 48
Transition table      383
Transitive closure      see Reflexive and transitive closure
Transitivity      7
Translation lemma      302—305
Traveling salesman problem      341 368
TREE      3—4 (see also Derivation tree)
Treybig, L. B.      374
Trio      270—277 280
Truth-table reduction      214
Turing machine      9 146—176 179 181—183 193 201—204 221—223 285-319
Turing reduction      212—213
Turing, A. M.      176 216
Two-stack machine      171
Two-tape finite automaton      74
Two-tape Turing machine      292—295
Two-way finite automaton      36—42
Two-way infinite tape      159—161
Two-way nondeterministic finite automaton      51
Two-way pushdown automaton      121 124
Type 0 grammar      220—223
Ullian, J. S.      106 216
Ullman, J. D.      54 75 106 124 216 227 267—268 284 319 376 394
Uncountable set      6
Undecidable problem      178—216
union      5 28 59 131 180 230 246 265 278 280
Union theorem      310—312
Unit production      91
Universal Turing machine      181—185
Unrestricted grammar      see Type 0 grammar
Useless symbol      88—89
Valiant, L. G.      145 247 269 319
Valid computation      see Computation
Valid item      249
Variable, of a grammar      77 79 389
Vertex      2
Vertex cover problem      331—332
Viable prefix      249—252
Wang, H.      176
Wegbreit, B.      232
Wise, D. S.      145
Word      1
Wright, E. M.      57
Yamada, H.      54 319
Yannakakis, M.      374
Yasuhara, A.      176
Young, P. R.      176
Younger, D. H.      145 (see also CYK algorithm)
1 2
blank
Ðåêëàìà
blank
blank
HR
@Mail.ru
       © Ýëåêòðîííàÿ áèáëèîòåêà ïîïå÷èòåëüñêîãî ñîâåòà ìåõìàòà ÌÃÓ, 2004-2024
Ýëåêòðîííàÿ áèáëèîòåêà ìåõìàòà ÌÃÓ | Valid HTML 4.01! | Valid CSS! Î ïðîåêòå