Àâòîðèçàöèÿ
Ïîèñê ïî óêàçàòåëÿì
Hopcroft J.E., Ullman J.D. — Introduction to automata theory, languages, and computation
Îáñóäèòå êíèãó íà íàó÷íîì ôîðóìå Íàøëè îïå÷àòêó?
Íàçâàíèå: 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.
ßçûê: Ðóáðèêà: Ìàòåìàòèêà /Ñòàòóñ ïðåäìåòíîãî óêàçàòåëÿ: Ãîòîâ óêàçàòåëü ñ íîìåðàìè ñòðàíèö ed2k: ed2k stats Ãîä èçäàíèÿ: 1979Êîëè÷åñòâî ñòðàíèö: 426Äîáàâëåíà â êàòàëîã: 15.12.2013Îïåðàöèè: Ïîëîæèòü íà ïîëêó |
Ñêîïèðîâàòü ññûëêó äëÿ ôîðóìà | Ñêîïèðîâàòü ID
Ïðåäìåòíûé óêàçàòåëü
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)
Ðåêëàìà
|
|
Î ïðîåêòå