Главная    Ex Libris    Книги    Журналы    Статьи    Серии    Каталог    Wanted    Загрузка    ХудЛит    Справка    Поиск по индексам    Поиск    Форум   
blank
Авторизация

       
blank
Поиск по указателям

blank
blank
blank
Красота
blank
Hein J.L. — Theory of Computation: An Introduction
Hein J.L. — Theory of Computation: An Introduction



Обсудите книгу на научном форуме



Нашли опечатку?
Выделите ее мышкой и нажмите Ctrl+Enter


Название: Theory of Computation: An Introduction

Автор: Hein J.L.

Язык: en

Рубрика: Математика/

Статус предметного указателя: Готов указатель с номерами страниц

ed2k: ed2k stats

Год издания: 1996

Количество страниц: 573

Добавлена в каталог: 16.11.2009

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
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
1 2 3 4 5
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2024
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте