|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Hein J.L. — Theory of Computation: An Introduction |
|
|
|
| Предметный указатель |
Excluded middle, law of 203
Existential closure 145
Existential generalization 166
Existential instantiation 160
Existential quantifier 138
Expression 214
Expression, algebraic 100
Expression, lambda 442
Expression, reduction rule 440
Expression, rewrite rule 440
Expression, transformation rule 440
Extended context-sensitive grammar 439
Extensionality, principle of 181
Factorial function 64
Factoring 228
Family tree problem 225
Fibonacci numbers 70 97
FIFO property 109
Final state 268 304
Finite automata 268—307
Finite automata as output devices 280
Finite automata, accept 269 271
Finite automata, deterministic 268
Finite automata, equivalent states 301
Finite automata, final state 268
Finite automata, initial state 268
Finite automata, language of 269
Finite automata, linear bounded 436
Finite automata, Mealy machine 280
Finite automata, minimum-state DFAs 301
Finite automata, Moore machine 280
Finite automata, NFA to regular grammar 312
Finite automata, nondeterministic 271
Finite automata, pushdown 326—340
Finite automata, reject 269 271
Finite automata, start state 268
Finite automata, state 268
Finite automata, state transition function 271 273
Finite automata, transition table 284 287
Finite set 10
Finite sums 93
First set 351
First-order logic 173
First-order predicate calculus 138—169
First-order predicate calculus, atomic formula, atom 139
First-order predicate calculus, equivalence 146
First-order predicate calculus, existential quantifier 138
First-order predicate calculus, formal proofs 158—169
First-order predicate calculus, literal 152
First-order predicate calculus, meaning, semantics 140
First-order predicate calculus, renaming rule 149 167
First-order predicate calculus, restricted equivalences 150
First-order predicate calculus, term 139
First-order predicate calculus, universal quantifier 138
First-order predicate calculus, validity 143
First-order predicate calculus, well-formed formula 139
First-order theory 180
First-order theory with equality 180
First-order theory, partial order 184
Fischer, M.J. 489 552
Fixed point 37
Flagged variable 161
Floor function 26
Floyd, R.W. 199 552
Follow set 352
Formal reasoning system 126
Formal theory 127
Franklin, Benjamin 465
Free to replace 159
Free variable 140 443
Function 24—36
Function constants 139
Function, argument of 25
Function, arity of 25
Function, codomain of 25
Function, composition 29
Function, definition by cases 26
Function, definition of 24
Function, domain of 25
Function, equality 26
Function, if-then-else 26
Function, image of 25
Function, partial 28
Function, partial recursive 404 408
Function, pre-image, inverse image of 26
Function, primitive recursive 408
Function, range of 25
Function, recursively defined 62
Function, total 28
Function, tupling 29
Function, type 25
Function, value of 25
Fundamental conjunction 123
Fundamental disjunction 122
Fuzzy logic 203
Gallier, J. 228 555
Garey, M.R. 499 552
Generalized regular expression 489
Generator of a binary relation 75
Gentzen, G. 552
Geometric progression 97
Geometry 176
Glb see “Greatest lower bound”
Goal 232 235 236
Goedel numbering 400
Goedel, K. 185 400 552
Goethe, Johann Wolfgang von 205
Grammar 40
Grammar, ambiguous 47
Grammar, context-free 324
Grammar, derivation 40 43
Grammar, Derivation tree 41
Grammar, extended context-sensitive 439
Grammar, language of 43
Grammar, left factoring 345
Grammar, left-recursive 346
Grammar, leftmost derivation 43
Grammar, LL(k) 343
Grammar, LR(1) 357
Grammar, LR(K) 355 357
Grammar, nonterminals 42
Grammar, parse tree 41
Grammar, phrase-structure 437
Grammar, production 42
Grammar, recursive 45
Grammar, recursive production 44
grammar, regular 310—318
Grammar, rightmost derivation 43
Grammar, rule or production 40
Grammar, sentential form 43
Grammar, start symbol 40 42
Grammar, terminals 42
Grammar, type 0 439
Grammar, type 1 439
Grammar, type 2 439
Grammar, type 3 439
Grammar, unrestricted 437
Graph 19
Graph, acyclic 21
Graph, connected 21
Graph, directed, digraph 19
Graph, edge 19
Graph, multigraph 19
Graph, vertex, node 19
Graph, weighted 20
Greatest element 84
Greatest lower bound 84
Greibach normal form 372
Greibach, S.A. 372 552
Growth rates 475—482
| Growth rates, big oh 480
Growth rates, big omega 481
Growth rates, big theta 475
Growth rates, little oh 479
Growth rates, lower 479
Growth rates, same order 475
Halting problem 426
Hamilton, A.G. 552
Handle 356
Hasse diagram 84
Hasse, Helmut 84
Head of list 17 54
Head of string 57
Height 22
Hein, J.L. xv 552
High school algebra 99
Higher-order logic 171—177
Higher-order semantics 175
Higher-order unification 228 454
Higher-order wff 172
Hilbert, D. 176 185 431 552
Hilbert’s Tenth Problem 431
Hindley, J.R. 552
Hisab al-jabr w’al-muqabala 99
Hoare, C.A.R. 199 552
Homomorphism 112
Hopcroft, J.E. 553
Horn clause 235
HS see “Hypothetical syllogism”
Hypothesis 3 119 124
Hypothetical syllogism 126
id see “Instantaneous description”
Identifier 270
Identity element 102
Identity function 29
If and only if 7
If-then rule 192
If-then-else function 26
If-then-else rule 193
IFF see “If and only if”
Image 25
Immediate left recursion 346
Immediate predecessor 83
Immediate successor 83
Implication 119
Implies 3
Inconsistent 127
Indegree 19
Indirect left recursion 348
Indirect proof 131—133
Indirect proof rule 132
Individual constants 139
Individual variables 139
Induced relation 75
Inductive definition 52
Inductive definition, binary trees 59
Inductive definition, language of a grammar 57
Inductive definition, lists 54
Inductive definition, natural numbers 53
Inductive definition, product sets 60
Inductive definition, strings 56
Inductive proof 90
Inductive set 52
Inference rule 124
Inference rule, addition 126
Inference rule, binary resolution 228
Inference rule, conjunction 126
Inference rule, constructive dilemma 136
Inference rule, destructive dilemma 136
Inference rule, disjunctive syllogism 126
Inference rule, existential generalization 166
Inference rule, existential instantiation 160
Inference rule, factoring 228
Inference rule, hypothetical syllogism 126
Inference rule, modus ponens 125
Inference rule, modus tollens 125
Inference rule, paramodulation 228
Inference rule, resolution 206
Inference rule, simplification 126
Inference rule, universal generalization 163
Inference rule, universal instantiation 159
Infinite list 17
Infinite sequence 17
Infinite set 10
Infinite set, countable 32
Infinite set, diagonalization 35
Infinite set, uncountable 32
Infix expression 25 72
Informal proof 2
Initial functions 404
Initial stack symbol 326
Initial state 268
Injection 30
Injective function 30
Innermost redex 445
InOrder 69
Insert in a sorted list 98
Instance of a decision problem 483
Instance of a set 215
Instance of a wff 146
Instance of an expression 214
Instantaneous description 328
Integers 2 10
Interpretation 141
Interpreter for DFAs 286
Interpreter for NFAs 288
Interpreter for PDAs 339
Interpreter for Turing machines 393
Intersection, bags 15
Intersection, collection of sets 12 13
Intersection, properties 13
Intersection, sets 13
Intractable 485
Invalid 143
Inverse element 102
Inverse function 30
Inverse image 26
Invertible function 30
IP see “Indirect proof rule”
Irreflexive 73
Irreflexive partial order 83
Isomorphic 112
Isomorphism 112
Item 363
Johnson, D.S. 499 552
Kleene, S.C. 269 409 553
Knuth — Bendix completion 455—460
Knuth — Bendix completion, inference rules 457
Knuth — Bendix completion, procedure 457
Knuth — Bendix completion, specialization order 456
Knuth, D.E. 355 455 459 460 553
Kurki-Suonio, R. 355 553
Lambda calculus 442—454
Lambda calculus,  -conversion 447
Lambda calculus,  -reduction 447
Lambda calculus,  -reduction 447
Lambda calculus, abstraction 443
Lambda calculus, application 443
Lambda calculus, applicative order reduction 445
Lambda calculus, bound variable 443
Lambda calculus, closed expression 443
Lambda calculus, combinator 443
Lambda calculus, free variable 443
Lambda calculus, innermost redex 445
Lambda calculus, lambda expression 442
Lambda calculus, normal form 444
Lambda calculus, normal order reduction 445
Lambda calculus, outermost redex 445
Lambda calculus, redex 444
Lambda calculus, scope 443
|
|
|
| Реклама |
|
|
|
|
|
О проекте