Ding-Zhu D., Ker-I K. — Problem solving in automata, languages, and complexity :: Электронная библиотека попечительского совета мехмата МГУ

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

Авторизация

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

Ding-Zhu D., Ker-I K. — Problem solving in automata, languages, and complexity

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

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

Название: Problem solving in automata, languages, and complexity

Авторы: Ding-Zhu D., Ker-I K.

Аннотация:

Automata and natural language theory are topics lying at the heart of computer science. Both are linked to computational complexity and together, these disciplines help define the parameters of what constitutes a computer, the structure of programs, which problems are solvable by computers, and a range of other crucial aspects of the practice of computer science. In this important volume, two respected authors/editors in the field offer accessible, practice-oriented coverage of these issues with an emphasis on refining core problem solving skills.

Язык:

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

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

ed2k: ed2k stats

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

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

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

Операции: Положить на полку | Скопировать ссылку для форума | Скопировать ID

Предметный указатель

Language equation      6
Language, context-free      see "Context-free language"
Language, context-sensitive      314
Language, feasibly solvable      294
Language, linear      158
Language, quotient      61
Language, regular      see "Regular language"
Language, reversal of a      6
Language, Turing-acceptable      163
Language, Turing-decidable      164
Left-factoring      121
Left-linear grammar      96
Lexicographic ordering      216
Linear grammar      99
Linear language      158
Linear set      150
Linear speed-up theorem      290
Literal      342
LMA      see "Labeled Markov algorithm"
Longest Path (LP)      338
Lookahead set      119
lp      see "Longest Path"
Mathematical induction      13
MAX(L)      67 146
Max-3Sat      377
Max-3Sat-b      379
MAX-CLIQUE      376
MCG      see "Minimum Connectivity Graph"
MIN(L)      61 67
Min-VC      370
Minimization, bounded      204
Minimum Connectivity Graph (MCG)      361
Minimum DFA      70
multi-valued function      370
Multi-valued function, polynomial-time computable      370
N      168
Negation      324
Network SMT      384
NFA      see "Nondeterministic finite automata"
Nondeterministic finite automata (NFA)      38
Nondeterministic finite automata (NFA), $\varepsilon$ -closure      39
Nondeterministic finite automata (NFA), $\varepsilon$ -move      38
Nondeterministic finite automata (NFA), $\varepsilon$ -transition      38
Nondeterministic finite automata (NFA), accepting an input      39 40
Nondeterministic finite automata (NFA), computation path      38
Nondeterministic finite automata (NFA), computation tree      39
Nondeterministic finite automata (NFA), hanging      38
Nondeterministic finite automata (NFA), multiple-state transition      38
Nondeterministic finite automata (NFA), transition diagram      38
Nondeterministic Turing machine (NTM)      304
Nondeterministic Turing machine (NTM), accepting an input      304
Nondeterministic Turing machine (NTM), computation tree      304
Nondeterministic Turing machine (NTM), computing a function      319
Nondeterministic Turing machine (NTM), space complexity      308
Nondeterministic Turing machine (NTM), time complexity      308
Nonterminal symbol      89
NP      309 323
NP SPACE      309
NP-complete set      350
NP-complete set, search problem      371
NP-hard set      350
NSPACE(t(n))      308
NTIME(t(n))      308
NTM      see "Nondeterministic Turing machine"
Ogden's lemma      147
Optimization problem      373
Optimization problem, approximation      see "Approximation problem"
Optimization problem, polynomially bounded      373
Oracle      371
Pairing function      207
Parikh's lemma      150
Parse tree      109
Parsing      111
Parsing, top-down      111
Partial function      164
Partial recursive function      see "Recursive function"
Partition      361
Partition, even      361
PCP      see "Post Correspondence Problem"
PDA      see "Pushdown automata"
Planar Connected-VC-4      369
Planar Nonpolar-3Sat      370
Planar Polar-3Sat      369
Planar VC      369 383
Poly-log functions      283
Polygon, convex      383
Polygon, convex, rectilinear      383
Polynomial functions      283
Polynomial-time approximation scheme (PTAS)      375
Polynomial-time approximation scheme (PTAS), fully (FPTAS)      375
Polynomial-time computable function      337 370
Polynomial-time equivalence      341
Polynomially honest function      337
Positive closure      5
Post correspondence problem (PCP)      272
Predicate      204
Prefix      2
prefix(B)      336
Primality Testing (Prime)      334
Prime      see "Primality Testing"
Primitive recursion      200
Primitive recursive function      201 218
Primitive recursive set      215
Probabilistically checkable proofs      377
Product automata      33
Productive set      258
Program-size complexity      264
Projection function      200
Projection theorem      233
PTAS      see "Polynomial-time approximation scheme"
Pumping lemma, for context-free languages      143
Pumping lemma, for regular languages      80
Pumping lemma, for regular languages, strong form      81
Pushdown automata (PDA)      122
Pushdown automata (PDA), accepting an input      123 124
Pushdown automata (PDA), configuration      123
Pushdown automata (PDA), configuration, successor      123
Pushdown automata (PDA), deterministic      190
Pushdown automata (PDA), linear-bounded      142
Pushdown automata (PDA), product      138
Pushdown automata (PDA), two-stack      142
Quotient language      61
r(n)      207
r(n)-Approx-Clique      377
r-Approx- $\Pi$       375
r-Approx-3Sat      377
r-Approx-3Sat-3      379
r-Approx-TSP      376
r-Approx-VC      377
r-Approx-VC-d      379
R. e. set      see "Recursively enumerable set"
RAM      see "Random access machine"
Random access machine (RAM)      191
REC      245
Rectangular partition      383
Rectilinear SMT      383
Recursion theorem      258
Recursive definition      13
Recursive function(s)      215
Recursive function(s), partial      215 218
Recursive function(s), partial, enumeration of      228
Recursive function(s), partial, extendable      243
Recursive function(s), primitive      201 218
Recursive set      215 218
Recursive set, primitive      215
Recursively enumerable (r.e.) set(s)      215 218
Recursively enumerable (r.e.) set(s), complete      251
Recursively enumerable (r.e.) set(s), enumeration of      228 232
Recursively separable sets      246
Reducibility      246

Reducibility, approximation-preserving      375
Reducibility, many-one      246
Reducibility, many-one, polynomial-time      340
Reducibility, polynomial-time      340
Reducibility, Turing, polynomial-time      371
Reduction function      246
Reg      253
Regular expression      8
Regular Expression Nonequivalence      369
Regular expression, disjunctive normal form      14
Regular expression, distributive law      9
Regular expression, extended      313
Regular expression, preference rules      9
Regular expression, starless      313
Regular grammar      97
Regular language      8
Regular set      8
rev      253
Reversal, of a language      6
Reversal, of a language, of a string      2
Rice's theorem      252
Rice's theorem, for r. e. index sets      256
Right-linear grammar      96
S-m-n theorem      248
SAT      see "Satisfiability"
Satisfiability (Sat)      325
Savitch's theorem      309
Search problem      370
Search problem, NP-complete      371
Self-recognizing program      265
Self-referential program      259
Self-reproducing program      262
Semi-characteristic function      215
Semilinear set      150
Sentence      89 90
Sentential form      89 90
Sentential form, left      111
Set-index set      251
Set-index set, nontrivial      252
SGIso      see "Subgraph Isomorphism"
Simple set      244
size(n)      209
SMT      see "Steiner Minimum Tree"
Space complexity      288
Space hierarchy theorem      297
Space hierarchy theorem, for NSPACE      311
Space marking machine      297
Space-constructible function, fully      297
Spanning tree      368
SQRT(L)      67 179
Star closure      4
Steiner minimum tree      366
Steiner Minimum Tree (SMT)      366
Steiner tree      365
Steiner tree, Steiner points      366
Steiner tree, terminal points      365
String      1
String, binary      1
String, empty      2
String, Length      2
Subexponential functions      283
Subgraph Isomorphism (SGIso)      350
Subset construction      46
Substitution      60
Substring      2
Subtraction, of sets      3
Successor function      200
Suffix      2
Superexponential functions      284
Symbol      1
T-Approx-BST      381
t-Approx-LP      385
Tape compression theorem      288
Terminal symbol      89
Three-dimensional matching      332
Three-Dimensional Matching (3DM)      332
Threshold function      338
Tiling      278
Time complexity      288
Time hierarchy theorem      300
Time-constructible function, fully      300
TM      see "Turing machine"
TOT      243
Total function      164
Tower of Hanoi      281
Transition diagram      24
Traveling salesman problem (TSP)      339 376
Traveling Salesman Problem (TSP), with (1,2)-Distance      384
Traveling Salesman Problem (TSP), with Triangle Inequality      384
TREE      365
Truth assignment      325
Truth table      324
TSP      see "Traveling Salesman Problem"
Turing machine(s) (TM, DTM)      159
Turing machine(s) (TM, DTM), accepting an input      162
Turing machine(s) (TM, DTM), coding of      226
Turing machine(s) (TM, DTM), computation path      162
Turing machine(s) (TM, DTM), computing a function      164
Turing machine(s) (TM, DTM), configuration      161
Turing machine(s) (TM, DTM), configuration, successor      161
Turing machine(s) (TM, DTM), deterministic (DTM)      159
Turing machine(s) (TM, DTM), enumeration      225
Turing machine(s) (TM, DTM), instructions      160
Turing machine(s) (TM, DTM), legal code of a      226
Turing machine(s) (TM, DTM), memory space      287
Turing machine(s) (TM, DTM), multi-tape      183
Turing machine(s) (TM, DTM), multi-tape, configuration      183
Turing machine(s) (TM, DTM), multi-tape, transition function      183
Turing machine(s) (TM, DTM), nondeterministic      see "Nondeterministic Turing machine"
Turing machine(s) (TM, DTM), one-pebble      179
Turing machine(s) (TM, DTM), output      164
Turing machine(s) (TM, DTM), product      233
Turing machine(s) (TM, DTM), read-only      173
Turing machine(s) (TM, DTM), read-only, crossing sequence      173
Turing machine(s) (TM, DTM), read/erase-only      180
Turing machine(s) (TM, DTM), running time      286
Turing machine(s) (TM, DTM), space bound      287
Turing machine(s) (TM, DTM), standard one-worktape      287
Turing machine(s) (TM, DTM), state      160
Turing machine(s) (TM, DTM), state, final      160
Turing machine(s) (TM, DTM), state, initial      160
Turing machine(s) (TM, DTM), tape      159
Turing machine(s) (TM, DTM), tape alphabet      160
Turing machine(s) (TM, DTM), tape, input      287
Turing machine(s) (TM, DTM), tape, one-way write-only      236
Turing machine(s) (TM, DTM), tape, output      287
Turing machine(s) (TM, DTM), tape, read-only      183
Turing machine(s) (TM, DTM), tape, storage      287
Turing machine(s) (TM, DTM), tape, tracks      181
Turing machine(s) (TM, DTM), tape, work      287
Turing machine(s) (TM, DTM), time bound      286
Turing machine(s) (TM, DTM), transition diagram      163
Turing machine(s) (TM, DTM), transition function      160
Turing machine(s) (TM, DTM), two-dimensional      189
Turing machine(s) (TM, DTM), two-way      181
Turing machine(s) (TM, DTM), two-way-infinite one-tape      181
Turing machine(s) (TM, DTM), universal      228
Turing-acceptable language      163
Turing-computable function      164 168 171
Turing-decidable language      164
Turing-enumerable set      236
Ultimately periodic set      69
Unbounded minimization      215
Undecidable problem      243 251 266
Undirected graph      328
union      3
Universal quantifier, bounded      204
Universal Turing machine      228
Unrestricted grammar      193
Unsolvability, degree of      254

1 2 3

О проекте