|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Hein J.L. — Theory of Computation: An Introduction |
|
|
|
| Предметный указатель |
Lambda calculus, weak-head normal form 453
Lambda calculus, Y combinator 452
Lambda closure 295
Lambda expression 442
Language 37
Language of a grammar 43
Language, closure 39
Language, context-free 324—325 369—378
Language, context-sensitive 436
Language, deterministic context-free 343
Language, hierarchy 435—439
Language, morphism 112 114 318 320 377
Language, nonregular 315
Language, positive closure 39
Language, product 38
Language, recursively enumerable 437
Language, regular 260—264 310—318
Language, well-formed formula 38
Laws of exponents 65
LBA see “Linear bounded automaton”
Leaf 22
Least element M
Least upper bound 85
Lee, R.C. 226 551
Left factoring 345
Left subtree 22
Left-recursive grammar 346
Left-recursive grammar, immediate 346
Left-recursive grammar, indirect 348
Leftmost derivation 43
Length, list 16
Length, path, walk, trail 21
Length, string 18
Length, tuple 15
Lewis, P.M. 343 553
LIFO property 326
Lin, S. 396 553
Linear bounded automaton 436
Linear order 82
Linearly ordered set 82
LIST 16—17 54 65 450
List, cons 54
List, empty 16
List, head 17 54
List, infinite 17
List, length 16
List, stream 17
List, tail 17 54
Literal 122 152 206
Little oh 479
LL(k) grammar 343
LL(k) parsing 343—355
LOG function 27
Logarithm see “Log function”
Logic program 236
Logic programming 254
Logic programming language 415
Logic programming, atom 231
Logic programming, backtracking 245
Logic programming, breadth-first search strategy 249
Logic programming, clause 235
Logic programming, computation tree 244
Logic programming, depth-first search strategy 245
Logic programming, functions 251
Logic programming, goal 232 236
Logic programming, program 236
Logic programming, relations 250
Logic programming, SLD-resolution 240
Logic programming, techniques 250—254
Logic, Absorption laws 121
Logic, DeMorgan’s laws 121
Logic, first-order 173
Logic, first-order predicate calculus 138
Logic, fuzzy 203
Logic, higher-order 171—177
Logic, modal 203
Logic, monadic 228
Logic, n-valued 203
Logic, nth-order 174
Logic, partial order theory 184
Logic, program 236
Logic, program clause 235
Logic, three-valued 203
Logic, two-valued 203
Logic, zero-order 173
Lookahead symbol 343
Loop invariant 194
Lower bound M
LR(1) grammar 357
LR(1) parse table 365
LR(1) parsing 360
LR(k) grammar 355 357
LR(k) parsing 355—368
Lub see “Least upper bound”
Lucas numbers 97
Lucas, Edouard 97
Lukasiewicz, J. 202 553
Lusk, E. 228 555
L’Hopital’s Rule 479
Mallows, C.L. 70 553
Manna, Z. 553
Mapping see “Function”
Markov algorithm 410
Markov, A.A. 412 553
Marxen, H. 396 553
Mathematical induction 91 94
Matiyasevich, Y. 431
Matrix multiplication 468
Maximal element 84
Mealy machine 280
Mealy, G.H. 280 554
Meaning of a wff 142
Member 9 15
Memoization 454
Mendelson, E. 554
Meyer, A.R. 490 554
Mgu see “Most general unifier”
Minimal element 84
Minimalization rule 408
Minimum condition 87
Minsky, M.L. 554
Modal logic 203
Model 143 398
modus ponens 125
Modus Tollens 125
Monadic logic 228
Monomorphism 112
Monotonic 456
Monus operation 113
Moore machine 280
Moore, E.F. 280 554
Morales-Bueno, R. 433 554
Morphism 110 112—113
Morphism, epimorphism 112
Morphism, homomorphism 112
Morphism, isomorphism 112
Morphism, language 112 114 318 120 177
Morphism, monomorphism 112
Most general unifier 217
MP see “Modus ponens”
MT see “Modus tollens”
Multigraph 19
Multiset 14
Myhill, J. 101 554
n-ary relation 72
n-tuple 15
n-valued logic 203
Nagel, E. 186 554
Natural numbers 10 53 63—65 450
Necessary condition 3
| Negation 2 105 119
Negative literal 206
Nerode, A. 301 554
Newman, J.R. 186 554
NFA see “Nondeterministic finite automaton”
Nivat, M. 460 551
Node 19 22
Noether, Emmy 87
Nondeterministic algorithm 485
Nondeterministic finite automaton 271
Nondeterministic finite automaton as an algebra 288
Nondeterministic PDA 327
Nondeterministic Turing machine 391
Nonregular languages 315
Nonterminals 42
NOR see “Normal order reduction”
Normal form 151 444
Normal form, conjunctive 122
Normal form, disjunctive 123
Normal form, fundamental conjunction 123
Normal form, fundamental disjunction 122
Normal form, prenex 151
Normal form, prenex conjunctive 152
Normal form, prenex disjunctive 153
Normal order reduction 445
NOT see “Negation”
NP 485
NP-complete 491
NPTIME 497
nth-order logic 174
Null set 9
Numeral 18
Numeral, binary 18 49 61
Numeral, decimal 18 49
Numeral, Roman 18
Object 9 15
One-to-one correspondence 30
One-to-one function 30
Onto function 30
Operator see “Function”
Optimal algorithm, problem 466
Optimal algorithm, worst case 467
OR see “Disjunction”
Order of a predicate 173
Order of a quantifier 174
Order of a wff 174
Order, lower 479
Ordered pair 15
Ordered tree 22
Ordered triple 15
Outdegree 19
Outermost redex 445
Overbeek, R. 228 555
P (class) 484
P (premise) 128
P for IP 132
Palindrome 61
Pan, V. 468 554
Pancake recipe 81
Parallel computation 81 417
Parallel language 417
Paramodulation 228
Parent 22
parse 40
Parse tree 41
Parsing 342—368
Parsing, bottom-up 343
Parsing, first set 351
Parsing, follow set 352
Parsing, handle 356
Parsing, item 363
Parsing, LL(1) parse table 353
Parsing, LL(k) 343—355
Parsing, lookahead symbol 343
Parsing, LR(1) 360
Parsing, LR(1) table 365
Parsing, LR(k) 355—368
Parsing, recursive descent 349
Parsing, shift-reduce 361
Parsing, top-down 343
Partial correctness 196
Partial function 28
Partial order 82—88
Partial order theory 184
Partial order, ascending chain 83
Partial order, chain 83
Partial order, descending chain 83
Partial order, greatest element 84
Partial order, greatest lower bound 84
Partial order, Hasse diagram 84
Partial order, immediate predecessor 83
Partial order, immediate successor 83
Partial order, irreflexive 83
Partial order, least element 84
Partial order, least upper bound 85
Partial order, lower bound 84
Partial order, maximal element 84
Partial order, minimal element 84
Partial order, minimum condition 87
Partial order, poset diagram 84
Partial order, predecessor 83
Partial order, reflexive 83
Partial order, set, poset 82
Partial order, successor 83
Partial order, upper bound 85
Partial recursive functions 404—409
Partially decidable 425 433
Partially ordered set 82
Partially solvable 425 433
Partition 78 79
Pascal, Blaise xiii
Paterson, M.S. 228 554
Path 21
Pattern-matching definition 63
Paulson, L.C. 554
PDA see “Pushdown automata”
Phrase-structure grammar 437
Pigeonhole Principle 315
Plus operation 405
Polish notation 202
Polynomial algebra 104
Polynomial time complexity 497
Polynomially reducible 490 498
Pope, Alexander 259
POSET see “Partially ordered set”
Poset diagram 84
Positive literal 206
Post algorithm 412
Post canonical system 414
Post system 414
Post, E.L. 412 430 554
Post-computable 415
Postcondition 188
Postorder 70
Post’s correspondence problem 430
Power set 11
Pre-image 26
Precedence hierarchy 120 139
Precondition 188
Predecessor 83
Predicate 137
Predicate constants 139
Predicate, order of 173
Premise 119 124
Prenex, conjunctive normal form 152
Prenex, disjunctive normal form 153
Prenex, disjunctive/conjunctive normal form algorithm 153
Prenex, normal form 151
Prenex, normal form algorithm 151
Preorder 68
|
|
|
| Реклама |
|
|
|
|
|
О проекте