|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Hein J.L. — Theory of Computation: An Introduction |
|
|
|
| Предметный указатель |
 -reduction 447
 -reduction 447
a-conversion 447
AA see “Assignment axiom”
Absorption laws 121
Abstract data type 106—110
Abstract data type, lists 108
Abstract data type, natural numbers 107
Abstract data type, queues 109
Abstraction 443
ACCEPT 269 271 328 383
Ackermann, W. 185 552
Ackermann’s function 98 409
Acyclic graph 21
Add see “Addition rule”
Addition rule 126
Adjacent vertices 19
Ait-Kaci, H. 460 551
Ait-Kaci, H., al-Khowarizmi 99
Algebra 99 100—113
Algebra, boolean 105
Algebra, carrier of 100
Algebra, definition of 100
Algebra, expression 100
Algebra, high school 99
Algebra, morphism 112
Algebra, polynomials 104
Algebra, regular expressions 265
Algebra, signature of 101
Algebra, vectors 104
Algebraic expression 100
Algorithm 99
Alphabet 17
Ambiguous grammar 47
AND see “Conjunction”
Andrews, P.B. 551
Antecedent 119 124
antisymmetric 73
AOR see “Applicative order reduction”
Append operation 56
Applicative order reduction 445
Applying a substitution 215
Apt, K.R. 199 551
Arithmetic progression 98
Arity 25
Artin, Emil 87
Ascending chain 83
Assignment axiom 189
Asymptotic behavior 475
atom 139 231
Atomic formula 139
Attributes 72
Automata see “Finite automata” “Pushdown
Axiom 104 126
Backtracking 245
Backwards check 165
Bag 14
Bag, intersection 15
Bag, union 15
Balanced parentheses 414
Basic equality 73
Bendix, P. 455 459 460 553
Bernstein, F. 33
Big oh 480
Big Omega 481
Big theta 475
Bijection 30
Bijective function 30
binary function 25
Binary relation 72—88
Binary relation, antisymmetric 73 74
Binary relation, basic equality 73
Binary relation, closure 75
Binary relation, composition 74
Binary relation, converse 76
Binary relation, equivalence 77
Binary relation, generator of 75
Binary relation, irreflexive 73
Binary relation, linear order 82
Binary relation, partial order 82
Binary relation, reflexive 73
Binary relation, reflexive closure 76
Binary relation, symmetric 73
Binary relation, symmetric closure 76
Binary relation, total order 82
Binary relation, transitive 73
Binary relation, transitive closure 76
Binary resolution 228
Binary search 470
Binary tree 22 59 68—70
Binary tree, inorder traversal 69
Binary tree, left subtree 22
Binary tree, postorder traversal 70
Binary tree, preorder traversal 68
Binary tree, right subtree 22
Binding 141 214
Boole, George 105
Boolean algebra 105
Boolean type 448
Bottom-up parsing 343
Bound variable 140 443
Boyle, J. 228 555
Brady, A.H. 396 551
Branch 22
Brassard, G. 551
Bratley, P. 551
Breadth-first search strategy 249
Buntrock, J. 396 553
Busy beaver 395 432
Busy Beaver function 432
Calculus 118
Call by name 445
Call by value 445
Cantor, Georg 31 33
Cardinality 30 31
Carrier 100
Carroll, Lewis 117
Case definition of function 26
cat see “Concatenation”
CD see “Constructive dilemma”
Ceiling function 26
Chain 83
Chang, C. 226 551
Children 22
Chomsky normal form 371
Chomsky, N. 371 439 551
Church — Rosser property 442
Church — Turing thesis 399 417
Church, A. 399 442 551
Churchill, Winston 421
Clausal form 206
Clause 206
Closed expression 443
Closure of binary relation 75
Closure, existential 145
Closure, inductive definition 52
Closure, lambda 295
Closure, language 39
Closure, positive 39
Closure, reflexive 76
Closure, symmetric 76
Closure, transitive 76 250
Closure, universal 145
CNF see “Conjunctive normal form”
CNF-satisfiability problem 491
CNF-satisfiability problem, 1-satisfiability 499
CNF-satisfiability problem, 2-satisfiability 494
CNF-satisfiability problem, 3-satisfiability 492
Codomain 25
Collection 9
| Combinator 443
Comparable 82
Comparison sorting 473
Complement, Boolean algebra 105
Complement, set 14
Completeness 185
Completion procedure 457
complexity 465
Component 15
Composition of binary relations 74
Composition of functions 29
Composition of statements 190
Composition of substitutions 215
Composition rule 190 404
Computability 398 422
Computable 398
Computation 398
Computation tree 244
Concatenation of strings 38
Conclusion 3 119 124
Conditional 119
Conditional proof 128—131
Conditional proof rule 128
Conditional statement 3
CONJ see “Conjunction rule”
Conjunction 3 119
conjunction rule 126
Conjunctive normal form 122
Connected 21
Connective 119 139
Cons function 54
Consequence rule 190
Consequent 119 124
Consistent 127
Constructive dilemma 136
constructor 53
Context-free grammar 324
Context-free language 324—325 369—378
Context-free language, Chomsky normal form 371
Context-free language, Greibach normal form 372
Context-free language, properties 377
Context-free language, removing A productions 370
Context-sensitive language 436
Contingency 120
Contradiction 7 120
Contrapositive 4
CONVERSE 4
Converse of binary relation 76
Conway’s challenge sequence 70
Cook, S.A. 491 552
Cook’s theorem 491
Coppersmith, D. 468 552
Correct program 188
Countable 32
Countably infinite 32
Counterexample 5
Countermodel 143
cp see “Conditional proof rule”
Cross product 16
CYCLE 21
Dag see “Directed acyclic graph”
DD see “Destructive dilemma”
De Morgan’s laws, logic 121
De Morgan’s laws, sets 14
Decidable 425
Decision problem 425 483
Decision problem, instance 483
Decision problem, length 484
Decision problem, no-instance 484
Decision problem, solution 484
Decision problem, yes-instance 484
Decision tree 470—473
Degree 19
Delete function 254
Delong, H. 552
Depth 22
Depth-first search strategy 245
Derivation 40 43
Derivation tree 41
Descartes, Rene 16
Descending chain 83
Destructive dilemma 136
Destructors 54
Deterministic algorithm 484
Deterministic context-free language 343
Deterministic finite automaton 268
Deterministic finite automaton as an algebra 285
Deterministic PDA 327
Deterministic Turing machine 391
DFA see “Deterministic finite automaton”
Diagonalization 35
Difference 14
Digraph 19
Dilemmas 136
Direct proof 6
Directed acyclic graph 21
Directed graph 19
Directed multigraph 19
Disagreement set 217
Disjoint sets 13
Disjunction 3 119
Disjunctive normal form 123
Disjunctive syllogism 126
divides 2
DNF see “Disjunctive normal form”
Domain 25 141
Doyle, Arthur Conan 1
DPTIME 497
DS see “Disjunctive syllogism”
EA see “Equality axiom”
EDGE 19
EE see “Equals for equals”
Effective enumeration 422—425
Effective enumeration, computable functions 425
EG see “Existential generalization”
EI see “Existential instantiation”
Element 9 15
Ellipsis 9
Embedding 30
Empty clause 206
Empty list 16
Empty relation 72
Empty set 9
Empty string 18
Empty substitution 214
Empty tuple 15
Epimorphism 112
Equal, bags 15
Equal, functions 26
Equal, regular expressions 264
Equal, sets 9
Equal, tuples 15
Equality 180—184
Equality, axiom 180
Equality, axioms for terms 182
Equality, basic 73
Equals for equals 180
Equipotent 31
Equivalence class 78
Equivalence of states 301
Equivalence problem 429
Equivalence relation 77
Equivalence relation, quotient 79
Equivalence relation, smallest 80
Equivalence, algebraic expressions 101
Equivalence, computational models 399
Equivalence, first-order predicate calculus 146
Equivalence, propositional calculus 121
Equivalence, Turing machines 388
Euclid 176
|
|
|
| Реклама |
|
|
|
|
|
О проекте