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

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

blank
blank
blank
Красота
blank
Salomaa A. — Computation and automata
Salomaa A. — Computation and automata

Читать книгу
бесплатно

Скачать книгу с нашего сайта нельзя

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



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


Название: Computation and automata

Автор: Salomaa A.

Аннотация:

This introduction to certain mathematical topics central to theoretical computer science treats computability and recursive functions, formal languages and automata, computational complexity, and cruptography. The presentation is essentially self-contained with detailed proofs of all statements provided. Although it begins with the basics, it proceeds to some of the most important recent developments in theoretical computer science.


Язык: en

Рубрика: Computer science/Вычислимость/

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

ed2k: ed2k stats

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

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

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

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID
blank
Предметный указатель
$\mathfrak{NP}$-complete      167
$\mathfrak{NP}$-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, $\lambda$-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 ($\downarrow$)      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($\uparrow$)      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
blank
Реклама
blank
blank
HR
@Mail.ru
       © Электронная библиотека попечительского совета мехмата МГУ, 2004-2017
Электронная библиотека мехмата МГУ | Valid HTML 4.01! | Valid CSS! О проекте