|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Hein J.L. — Theory of Computation: An Introduction |
|
|
|
| Предметный указатель |
Presburger arithmetic 488
Preserve an operation 111
Prime number 2
Prime number theorem 95
Primitive recursion rule 405
Primitive recursive function 408
Procedure 61 66 69
Procedure, recursively defined 62
Product of sets 16
Product, cartesian 16
Product, cross 16
Product, language 38
Product, matrix 468
Product, notation 64
Product, set 60
Production 40
Production, indirectly recursive 44
Production, recursive 44
Program correctness 187—199
Program correctness, assignment axiom 189
Program correctness, composition rule 191
Program correctness, consequence rule 190
Program correctness, correct program 188
Program correctness, if-then rule 192
Program correctness, if-then-else rule 193
Program correctness, loop invariant 194
Program correctness, partial 196
Program correctness, postcondition 188
Program correctness, precondition 188
Program correctness, termination 198
Program correctness, total 196
Program correctness, while rule 194
proof 2 90 127 158 187—199 225—227
Proof by contradiction 7 131
Proof, conditional proof rule 128
Proof, contrapositive 6
Proof, direct 6
Proof, if and only if 7
Proof, indirect 131—133
Proof, inductive 90
Proof, informal 2
Proof, mathematical induction 91 94
Proof, multiple variable induction 96
Proof, reductio ad absurdum 131
Proof, refutation 7
Proof, resolution 213
Proof, structural induction 95
Proof, using variables 5
Proof, well-founded induction 94
Proper subset 11
Proposition 118
Propositional calculus 118—134
Propositional calculus, equivalence 121
Propositional calculus, normal forms 122
Propositional calculus, proposition 118
Propositional calculus, semantics 120
Propositional calculus, syntax 119
Propositional calculus, well-formed formula (wff) 119
Propositional variables 119
PSPACE 486
Pumping lemma, context-free languages 374
Pumping lemma, regular languages 316 317
Pushdown automata 326—340
Pushdown automata as an algebra 339
Pushdown automata, accept 328
Pushdown automata, deterministic 327
Pushdown automata, instantaneous description 328
Pushdown automata, interpreter 340
Pushdown automata, nondeterministic 327
Pushdown automata, pushdown transducer 350
Pushdown automata, reject 328
Pushdown transducer 350
QBF see “Quantified Boolean Formula Problem”
qed xv
Quantified boolean formula 487
Quantified Boolean Formula Problem 487
Quantifier, existential 138
Quantifier, order of 174
Quantifier, scope 140
Quantifier, symbols 139
Quantifier, universal 138
Quasi-order 83
QUEUE 109
Rabin, M.O. 271 489 552 554
Rado, T. 396 432 553 554
RANGE 25
rat see “Reflexive partial order”
Rational numbers 10
Real numbers 10
Recognition problem 259
recursive descent 349
Recursive grammar 45
Recursive production 44
Recursively defined function 62
Recursively defined procedure 62
Recursively enumerable language 437
Redex 444
Reduce 440
Reductio ad absurdum 131
Reduction rule 440
Reduction sequence 440
Reflexive 73
Reflexive closure 76
Reflexive partial order 83
Refutation 7
Regular expression 261—266 489
Regular expression, equality 264
Regular expression, properties 264
Regular grammar 310—318
Regular language 260—264 310—318
Regular language, properties 318
Reject 269 271 328 383
Relation 71
Relation, attributes 72
Relation, empty 72
Relation, n-ary 72
Relation, universal 72
Relative complement 14
Renaming rule 149 167
Replacement rule 122
Resolution 212—213 219—227
Resolution for set of clauses 223
Resolution, proof 213
Resolution, the general case 219
Resolution, theorem 224
Resolvant 221
Reverse of string 49
Reversing a string 411
Rewrite 440
Rewrite rule 440
Right subtree 22
Robinson, J.A. 218 224 228 554
Root 22
Rosenkrantz, D.J. 355 555
RST see “Equivalence relation”
Ruskin, John 51
Russell, B. 202 381 555
Satisfiable 143
Schoenfield, J.R. 555
Schoening, U. 555
Schroeder, E. 33
Scope 140 443
Scott, D. 271 554
Semantics, higher-order logic 175
Semantics, propositional wffs 120
Semantics, quantified wffs 142
Sentential form 43 344
SEQUENCE 15
Set 9
Set, cardinality 30
| Set, complement 14
Set, countable 32
Set, countably infinite 32
Set, De Morgan’s laws 14
Set, difference 14
Set, disjoint 13
Set, empty 9
Set, equality 9
Set, finite 10
Set, inductive definition 52
Set, infinite 10
Set, intersection 13
Set, null 9
Set, power set 11
Set, product 16 60
Set, proper subset 11
Set, relative complement 14
Set, singleton 9
Set, subset 11
Set, symmetric difference 14
Set, uncountable 32
Set, union 12
Set, universe 14
Shepherdson, J.C. 402 555
Shift-reduce parsing 361
Sign function 406
Signature 101
Signum function 406
simp see “Simplification rule”
Simple language 402
Simple sort 469
Simplification rule 126
SIMPLIFY 440
Singleton 9
Sink 19
Skolem Functions 208
Skolem, T. 207 555
Skolem’s algorithm 209
Skolem’s rule 208
SLD-resolution rule 240
Snyder, W. 228 555
solvable 425
Soundness 185
Source 19
Space complexity 497
Specialization ordering 456
STACK 326
Start state 268 304
Start symbol 40 42
State 268
State of a computation 197
State transition function 271 273
Stearns, R.E. 343 355 553 555
STIRLING, JAMES 478
Stirling’s formula 478
Stockmeyer, L.J. 490 554
Strassen, V. 468 555
Stream 17
String 17 56—57 66—67
String, alphabet 17
String, append 56
String, concatenation 38
String, empty 18
String, head 57
String, Length 18
String, tail 57
Structural induction 95
Sturgis, H.E. 402 555
Subproof 129
Subscripted variable 162
Subset 11
Substitution 214
Subtree 22
Succ see “Successor function”
Successor 83
Successor function 53
Sufficient condition 3
Summation notation 64
Suppes, P. 555
Surjection 30
Surjective function 30
symmetric 73
Symmetric closure 76
Symmetric difference 14
T (true statement) 130
Tail of list 17 54
Tail of string 57
Tautology 120
Term 139
Terminals 42
termination condition 198
Ternary relation 72
Theorem 127
Thompson, K. 292 555
Thoreau, Henry David 178
Three-valued logic 203
Time 496
Time complexity 496
Time-oriented task 82 85
Top-down parsing 343
Total correctness 196
Total function 28
Total order 82
Total problem 428
Totally ordered set 82
Tractable 485
Trail 21
Transformation see “Function”
Transformation rule 440
Transition table 284 287
Transitive 73
Transitive closure 76 250
Traveling salesman problem 483
TREE 21
Tree, binary tree 22
Tree, branch 22
Tree, child 22
Tree, height, depth 22
Tree, leaf 22
Tree, node 22
Tree, ordered 22
Tree, parent 22
Tree, root 22
Tree, subtree 22
Tree, unordered 22
Trivially true 4
Truth symbols 119
Truth table 2—4 119
Tuple 15
Tuple, empty 15
Tuple, equality 15
Tuple, length 15
Tuple, n-tuple 15
Tupling functions 29
Turing machine 382—395
Turing machine with outpput 386
Turing machine, accept 383
Turing machine, blank symbol 383
Turing machine, control unit 382
Turing machine, deterministic 391
Turing machine, equivalence 388
Turing machine, halt state 383
Turing machine, interpreter 393
Turing machine, language 383
Turing machine, multihead 388
Turing machine, multitape 388
Turing machine, nondeterministic 391
Turing machine, one-way infinite tape 388
Turing machine, reject 383
Turing machine, start state 383
|
|
|
| Реклама |
|
|
|
|
|
О проекте