|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Salomaa A. — Computation and automata |
|
|
|
| Предметный указатель |
 -complete 167
-hard 167
0L system 36
1-reducible 102
A-restriction 245
Acceptable enumeration 141
Accepting device 33
Algorithm 1
Almost everywhere 144
Alphabet 6
Alphabet of constants 24
Alphabet of variables 24
Analysis problem 40
Axiom 24
Bad-luck number 121
Binary notation 60
Blank symbol 79
Blum axioms 141
Boolean operations 6
Boundary marker 79
Caesar cipher 12 190
Capacity of place 236
Catenation 6
Catenation closure 7
Catenation closure,  -free 7
Catenation of languages 7
Characteristic function 87
Characteristic pair 157
Chomsky normal form 21 22
Church's thesis 77 78
Ciphertext 187
Clause 162
Cleartext 187
CLIQUE 184
Color-family 248
Complete grammar form 244
Complete set 102
Complete set, l-complete 104
Complete set, m-complete 104
complexity 139
Complexity class 147
Complexity function 141
Complexity measure 141
Complexity measure, machine-independent 142
Complexity, axiomatic 140
Complexity, low-level 140
Composition sequence 111
Compression theorem 149 150
Computational complexity 139
Cone 57
Conflict in Petri net 232
Conjunctive normal form 162
CONSAT 162
Context-free complete 244
Context-free grammar 18
Contraction 28
Converges ( ) 87
Corresponding function 112
Cost function 141
Counter automaton 73
Creative set 105
Cryptanalysis 189
Cryptanalysis, initial setups for 189
Cryptosystem 188
Cryptosystem, commutative 197
Cryptosystem, context-free 196
Cryptosystem, context-sensitive 196
Cryptosystem, knapsack 206
Cryptosystem, monoalphabetic 196
Cryptosystem, polyalphabetic 196
Cryptosystem, public key 196
Cryptosystem, RSA 217
Cryptosystem, skeletal public key 204
Cryptotext 187
Cube-free 38
D0L sequence 37
D0L system 36
Data Encryption Standard 195
decrypting 187
Degree of reducibility 102 104 110
Degree of set 127
Dense pair 248
Derivation 13
Derivation tree 16
DES 195
Deterministic language 68
DH-pair 196
Diagonalization 2
Diagonalization, dilemma of 2
Dimension of set 127
Diophantine 125
Diophantine relation 125
Diophantine set 125
Diverges( ) 87
Dovetailing 95
Dyadic notation 60 98
E0L system 38
Effective procedure 1
EIL system 39
Electronic signature 198
Emptiness problem 54
Empty pushdown tape 69
Empty word 6
Enabled 232
encrypting 187
Equivalence problem 54
Equivalent grammars 15
expansion 28
Expansion spectrum 247
Expansive nonterminal 247
Family equivalent 242
Final production 32
Finite automaton 46
Finite automaton, deterministic 46
Finite automaton, equivalence of 52
Finite automaton, nondeterministic 48
Firing in Petri net 232
Flipping coin by telephone 226
Gap theorem 148
Generalized sequential machine 54
Generalized sequential machine, deterministic 56
Generative device 33
Goedel number 84
Grammar 14 15
Grammar form 241 242
Grammar, context-free 18
Grammar, context-sensitive 18 41
Grammar, graph 264
Grammar, left-linear 74
Grammar, matrix 137
Grammar, reduced 245
grammar, regular 19
Grammar, regular pattern 264
Grammar, right-linear 74
Grammar, selective substitution 263
Grammar, self-embedding 245
Grammatical family 242
Graph grammar 264
Greibach normal form 263
Growth function 39
| Growth matrix 40
gsm mapping 56
Gsm mapping, inverse 56
halt 103
HALTING 32 79
Halting problem 88
Hilbert's tenth problem 124
Hill's cryptosystem 192 193
IL system 39
Inclusion problem 54
ind 143
Index for set 97
Index of function 84
Index of Turing machine 84
Infinity problem 54
Interpretation 242 243
Intractable 165
Key 188
Khachiyan's theorem 185
Kleene characterization 48
Knapsack 164
Knapsack vector 206
Knapsack vector, super-increasing 206
L systems 35
Language 6
Language, 0L 36
Language, accepted by Markov algorithm 34
Language, accepted by pushdown automaton 68
Language, accepted by systolic tree automaton 253
Language, accepted by Turing machine 79
Language, ADPDA 68
Language, AFDA 47
Language, AFNA 48
Language, alphabet of 6
Language, commutative 249
Language, context-free 18
Language, counter 73
Language, D0L 36
Language, defined by Petri net 238
Language, deterministic 68
Language, DRE 49
Language, E0L 38
Language, EIL 39
Language, exhaustive by Petri net 238
Language, generated by 0L system 36
Language, generated by grammar 15
Language, generated by Post system 25
Language, IL 39
Language, k-testable 75
Language, locally testable 75
Language, recursively enumerable 18
Language, regular 19
Las Vegas algorithm 221
Length of derivation 13
Length of word 6
letter 6
Letter, nonterminal 15
Letter, start 15
Letter, terminal 15
Linear grammar 244
Linear programming 185
Literal 162
Logarithmic space 182
Logarithmic space, complete 182
Looping 32 79
M-reducible 102
Marking 232
Marking, initial 232
Markov algorithm 31 32
Matrix grammar 137
Mealy machine 56
Measure-independent 160
Membership problem 54 55
Meyer — Fischer complexity sequence 160
Mirror image 17
Monte Carlo algorithm 221
Morphism 8
Morphism, inverse 57
Morphism, letter-to-letter 8
Morphism, nonerasing 8
n-adic notation 60
n-ary notation 60
Neutration 28
Nivat's theorem 59
Nonspeedable 159
Nonterminal 15
Normalization principle of algorithms 78
Number system 60
Number system, ambiguous 60
Number system, complete 60
Number system, unambiguous 60
one-time pad 195
Oracle 110
padding 103
Pairing function 87
Parallel rewriting 35
Partial function 80
Partial recursive function 80
Pebble game 183
Pebbling 183
Petri net 231
Petri net with multiplicities 238
Petri net with place capacities 235
Petri net, alive 238
Petri net, place-bounded 235
Place 232
Place, input 232
Place, output 232
Plaintext 187
Poker by telephone 223
Polynomially bounded TM 164 165
Polynomially equivalent 167
Polynomially isomorphic 175
Polynomially reducible 167
Polynomially space-bounded 177
Post (canonical) system 24
Post (canonical) system, pure 25
Post (canonical) system, reduced 28
Post (canonical) system, regular 26
Post Correspondence Problem 117
Post correspondence problem, solution of 117
Prefix 6
Presburger arithmetic 180
Primality testing 221
Processor 252
Production 13 24 32 36 68
Productive set 105
Projection of relation 114
Protocol 222
Public key cryptosystem 196
Public key cryptosystem, skeletal 204 205
Pumping lemma 62
Pumping lemma, context-free languages 63
Pumping lemma, converse of 65
Pumping lemma, regular languages 62
Pumping nonterminal 246
Pumping nonterminal, left 246
Pumping nonterminal, right 246
Pumping spectrum 246
Pure Post system 25
|
|
|
| Реклама |
|
|
|
|
|
О проекте