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
$\beta$-reduction      447
$\eta$-reduction      447
a-conversion      447
AA      see Assignment axiom
Absorption laws      121
Abstract data type      106110
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
Ackermanns 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 100113
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      7288
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 6870
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      128131
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      324325 369378
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
Conways challenge sequence      70
Cook, S.A.      491 552
Cooks 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 Morgans laws, logic      121
De Morgans 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      470473
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      422425
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      180184
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
1 2 3 4 5
blank
blank
blank
HR
@Mail.ru
       © , 2004-2017
   | Valid HTML 4.01! | Valid CSS!