Àâòîðèçàöèÿ
Ïîèñê ïî óêàçàòåëÿì
Davis M., Sigal R., Weyuker E. — Computability, complexity, and languages: Fundamentals of theoretical computer science
Îáñóäèòå êíèãó íà íàó÷íîì ôîðóìå Íàøëè îïå÷àòêó?
Íàçâàíèå: Computability, complexity, and languages: Fundamentals of theoretical computer scienceÀâòîðû: Davis M., Sigal R., Weyuker E.Àííîòàöèÿ: This introductory text covers the key areas of computer science, including recursive function theory, formal languages, and automata. It assumes a minimal background in formal mathematics. The book is divided into five parts: Computability, Grammars and Automata, Logic, Complexity, and Unsolvability. * Computability theory is introduced in a manner that makes maximum use of previous programming experience, including a "universal" program that takes up less than a page.* The number of exercises included has more than tripled.* Automata theory, computational logic, and complexity theory are presented in a flexible manner, and can be covered in a variety of different arrangements.
ßçûê: Ðóáðèêà: Computer science /Ñòàòóñ ïðåäìåòíîãî óêàçàòåëÿ: Ãîòîâ óêàçàòåëü ñ íîìåðàìè ñòðàíèö ed2k: ed2k stats Èçäàíèå: 2-nd editionÃîä èçäàíèÿ: 1994Êîëè÷åñòâî ñòðàíèö: 628Äîáàâëåíà â êàòàëîã: 30.03.2014Îïåðàöèè: Ïîëîæèòü íà ïîëêó |
Ñêîïèðîâàòü ññûëêó äëÿ ôîðóìà | Ñêîïèðîâàòü ID
Ïðåäìåòíûé óêàçàòåëü
273—274 278 278 215—230 215 217 215—230 215 217 1-completeness 209 226 Algorithms 3 68 79—80 95 411 Almost everywhere 421 Alphabets 4 113 347 375 505 Alphabets of linear bounded automata 330 Alphabets of pushdown automata 310 Alphabets of Turing machines 146 Approximation orderings 470—471 487 505 see "Partial Arithmetic hierarchy 215—230 Arithmetic predicates 223 Assignments, complete type 512 513 516 539 Assignments, continuous variable 514—515 539 Assignments, Herbrand ideal type 546 Assignments, on propositional atoms 348 406 455—456 Assignments, type 511—512 Assignments, variable 514—515 atoms 347 Automata theory 237 Axiom of Choice 474 Axiomatizable theories 407—410 415 Axiomatizable theories, 410 Axiomatizable theories, complete 410 Axiomatizable theories, consistent 410 Axiomatizable theories, nonrecursive 415 Balanced words 309—310 Bar-Hillel's pumping lemma 287—290 299 Base n notation 116 328 580 Binary relations 472 Binary relations, restrictions of 472 Blum axioms 419—425 Blum speedup theorem 437—438 Blum, Manuel 419 Boolean algebra 350 Bottom elements 477 Bracket languages 301—308 Cantor, Georg 406 Cartesian product 3 Case, John 103 Chains 477 499 Chang, C.L. 593 Chomsky hierarchy 327—330 Chomsky normal form grammars 285—287 287—290 297 303 306 308 313 316 319 Chomsky normal form grammars, separators of 303—308 313 319 Chomsky — Schuetzenberger representation theorem 306 Church's thesis 69 80 90 95 96 141 161 162 197 407 445 447 Church, Alonzo 411 clauses 355—356 Clauses, linked sets of 366—367 396 398 400 Clauses, minimally unsatisfiable sets of 366—367 392 395 Clauses, unit 361 362 363 Closure properties 4 Closure properties for context-free languages 291—297 Closure properties for context-sensitive languages 329 337—344 Closure properties for regular languages 249—256 CNF see "Conjunctive normal form" Co-NP 450 COBOL 323 Coding of 579—582 Coding of 579—582 Coding of 579—582 Coding of finite functions 203—204 580 Coding of pairs 59—60 see Coding of programs 65—67 Coding of sequences 60—63 see Coding of states of programs 71 Coding of strings 113—115 COF 227 Coincidence lemma 518 527 COMP 48 Compact elements of a cpo 486 Compactness theorem for predicate logic 390 404—406 Compactness theorem for propositional calculus 370—373 390 404 Compilers 323—326 Complete partial orders 475—486 516 see "Orderings" Complete partial orders, algebraic 486 494 Complete partial orders, compact elements of 486 Complete partial orders, flat 477 539 Complete partial orders, of continuous variable assignments 516—517 Complexity, abstract 419—438 Complexity, measures 419 composition 39—40 42 76 77 108 200 576 Computability theory 17 18 31 70 98 113 169 237 443 Computable real numbers 554 587 589—590 Computations, by 27 28 29 70—75 420 468 557 Computations, by linear bounded automata 339—343 Computations, by nondeterministic Turing machines 160 171 447—448 451—456 Computations, by pushdown automata 311—323 Computations, for W-terms 559—575 584—587 588 Computations, infinite 469—470 563 Configurations of linear bounded automata 330 331 Configurations of Post — Turing programs 130 Configurations of pushdown automata 311 Configurations of Turing machines 147 159—160 444 452—456 Conjunctive normal form 356—360 364 368 392 393 444 446 447—448 451—456 457—458 461 Constant symbols 375 506 Context-free grammars 269—280 326 327 497—499 see Context-free grammars, ambiguity of 300 303 307 319 Context-free grammars, branching 277 279 285 Context-free grammars, Chomsky normal form see "Chomsky normal form grammars" Context-free grammars, derivation trees in see "Derivation trees" Context-free grammars, derivations in 270 275 277 Context-free grammars, Greibach normal form 287 Context-free grammars, kernels of 271 Context-free grammars, languages generated by 270 Context-free grammars, left-linear 285 Context-free grammars, leftmost derivations in 275—277 Context-free grammars, positive 269 271 273 277 327 Context-free grammars, productions of 269 Context-free grammars, regular 280—285 327 Context-free grammars, right-linear 283 304 Context-free grammars, rightmost derivations in 275—277 Context-free grammars, self-embedding 284 Context-free grammars, unsolvable problems involving 297—301 Context-free languages 269—326 327—328 337 450 see Context-free languages, and compilers 323—326 Context-free languages, and pushdown automata 308—323 Context-free languages, closure properties for 291—297 Context-free languages, deterministic 323 Context-free languages, infinite 298—299 Context-free languages, inherently ambiguous 301 Context-free languages, nonregular 270 Context-free languages, regular 280—285 Context-sensitive grammars 189—190 327—330 Context-sensitive grammars, unsolvable problems involving 339 Context-sensitive languages 327—344 Context-sensitive languages, closure properties for 329 337—344 Context-sensitive languages, open questions concerning 343 Cook — Karp thesis 445 Cook's theorem 451—456 Corollaries 8 Correctness of operational semantics 557 Correctness of programs 536 Course-of-values recursion 62—63 CPO 477 see cpo, flat 477 Data structure systems 531 536 Data structure systems, infinitary 544—556 584—592 Data structure systems, simple 539—544 557—575 Davis — Putnam rules 360—366 368 391 393 396 444 Davis, Martin 593 de Morgan identities 2 6 7 50 251 291 350 354 371 380 Definition by cases 50—51 Degree of function symbols 375 Degree of polynomials 441 Degree of relation symbols 375 Derivation trees 274—279 298 498 Derivation trees, pruning and splicing of 279 289 DFA 243 see DFA, minimal 266 Diagonal Lemma 492 502 518 Diagonalization 88—90 94 106 328 406 429 Disjunctive normal form 356—360 444 DNF see "Disjunctive normal form" Dovetailing 80 81 408 DTIME 450 Duality, general principle of 350 356 358 380 Dyck languages 303 306 Empty program 26 Enderton, Herbert P. 593 Enumeration Principle 370 371 405 Enumeration theorem 81 Equivalence relations 263 Euclid 57 Exchange Lemma 490 491 503 EXPTIME 450 451 Extension Lemma 526—527 532 534 573 Fibonacci numbers 62 529 Finite automata 237—242 Finite automata, deterministic 243 280 292 Finite automata, nondeterministic 242—249 281 324 Finite automata, nonrestarting 250 316 Finite satisfiability 370—372 Finiteness theorem 204 First-order logic see "Quantification theory" Fixed point induction principle 499 see fixed Fixed point theorem 101 501 see Fixed point theorem for cpos 495—496 497 499 501 524 Fixed points 494—503 Fixed points as solutions to W-programs 523 Floyd, R.W. 181 Formulas, atomic 376 Formulas, ground 392 Formulas, Herbrand instances of 412—414 Formulas, in predicate logic 376 Formulas, propositional 347 496—500 Formulas, quasi-representing sets 409 Formulas, representing functions 410 Formulas, representing sets 408 409 Formulas, semantically equivalent 380 FORTRAN 279 323 324 Function symbols 375 506 Function symbols, arity of 506 Function symbols, built-in 509 Function symbols, constructor 509 Function symbols, degree of 375 Function symbols, discriminator 509 Function symbols, proper 506 Function symbols, selector 509 Functions 3 Functions, 574 575—584 Functions, binary 3 Functions, Boolean-valued 5 Functions, characteristic 6 78 see Functions, computable 28—32 41 42 77 112 116 121 469 567 Functions, computed by 19 22—25 30 Functions, computed by Post — Turing programs 134 135 140 141 147 149 150 Functions, computed by Turing machines 146—152 Functions, computed strictly 134 135 139 146 148 Functions, constructible 428 Functions, continuous 486—494 495 Functions, domain of 3 Functions, elementary 59 Functions, exponential 425 442 444 450 Functions, G-computable 198 Functions, G-partial recursive 198 Functions, G-recursive 198 Functions, higher order 470 481 520 Functions, intuitively computable see "Church's thesis" Functions, monotonic 487—494 Functions, n-ary 3 200 Functions, nowhere defined 3 31 Functions, on strings 116—117 Functions, one-one 4 84 Functions, onto 4 Functions, partial 3 24 Functions, partial recursive 30 84 Functions, partially computable 30 39 70 73 75 76 83 96 116 127 140 148 198 199 467 501 578—582 Functions, partially computable in 121 127 135 140 141 Functions, partially G-computable 198 Functions, polynomial time computable 445 Functions, primitive recursive 39—63 84 105—112 117 188 262 576—578 Functions, range of 3 82 83 84 functions, recursive 30 84 426 428 436 437 Functions, strict 487 539 564 Functions, strict extensions of 487 Functions, total 3 5 30 40 42 90 198 199 200 201 202 204 205 Functions, unary 3 G-r.e. sets 211—215 Gap theorem 425—428 Garey, Michael R. 593 Goedel numbers 60—63 66 67 71 74—75 79 84 108 200 204 217—218 222 232 435 580 Goedel's incompleteness theorem 407—410 Goedel, Kurt 60 Goldbach's conjecture 69 70 grammars 186—191 see "Context-sensitive "Regular Grammars, derivations in 188 270 Grammars, languages generated by 186 270 327—329 Grammars, left-linear 285 Grammars, null productions of 269 327 344 Grammars, phrase structure 186 327 Grammars, positive context-free 269 327 Grammars, productions of 186 269 Grammars, regular 280—285 327 Grammars, right-linear 283 304 Grammars, self-embedding 284 Grammars, start symbol of 186 269 Grammars, terminals of 186 269 Grammars, unsolvable problems concerning 191—192 300—301 322 339 Grammars, variables of 186 269 graphs 458—460 Graphs, cliques in 459 Graphs, complete 458—459 Greatest lower bounds 476 Greibach normal form grammars 287 Ground clauses 392 Ground resolution 369 see in Ground resolution theorem 369 Gunter, Carl A. 593 Halmos, Paul R. 593 Halting problem 68—70 78 82 89 97—98 99 197 467 488 523 554 see halting Halting problem for Post — Turing programs 144 Halting problem for Turing machines 157—158 Harrison, Michael 594 Herbrand instances of formulas 412—414 Herbrand universes 388 389 390 392 393 395 398 405 406 412 542 Herbrand's theorem 388—398 404 Hilbert, David 410 411 Homomorphisms 253 296 344 Horn clauses 403 Horn programs 404 Hrbacek, Karel 594 Ideals 482—483 546—556 Ideals, principal 482 552 Immerman, Neil 339 Index sets 95 103 230—231 Induction 9—13 Induction, complete 11—12 Induction, course-of-values 11—12 302 Induction, fixed point 499—500 536—537 Induction, hypothesis 10 Induction, loading 11 109 Induction, mathematical 9—13 52 86 206 215 245 256 264 271 293 304 305 433 495 540 571 576
Ðåêëàìà
-trees 
as a collection of sets 
-consistent 
-programs 
programs 
-computable 
|
|
Î ïðîåêòå