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

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

$(min\ i)_{i\leq m}$       204
$(\exists i)_{i\leq m}$       204
$(\forall i)_{i\leq m}$       204
$2^{S}$       38
$a\cdot b$       3
$A\oplus B$       67
$A\vee B$       62
$A^{+}$       5
$A^{k}$       4
$A^{R}$       6
$f(n) \prec g(n)$       283
$f^{(n)}$       202
$G|_{A}$       360
$I_{\sigma}$       216
$K^{i}_{j}$       201
$L_{1}/ L_{2}$       61
$L_{\frac{1}{2}}$       63
$M_{1}\times M_{2}$       33
$M_{n}$       228
$M_{x}$       228
$R^{*}_{L}$       75
$R_{l}$       70
$Space_{M}(x)$       308
$Time_{M}(x)$       286 308
$T_{n,k}$       338
$W_{n}$       228
$x\cdot y$       2
$x\vee y$       62
$x^{k}$       2
$x^{R}$       2
$[n_{1}, n_{2}, ..., n_{k}]$       209
$\chi_{L}$       164 215
$\equiv^{p}_{m}$       341
$\langle i, j \rangle$       207
$\langle n_{1}, n_{2}, ..., n_{k} \rangle$       209
$\leq^{p}_{m}$       340
$\leq^{P}_{T}$       371
$\leq_{m}$       246
$\mathcal{M}$       225
$\neg$       324
$\oplus$       67
$\overline{A}$       3
$\overset{*}{\vdash}$       123 162
$\phi^{k}_{n}$       228
$\pi^{k}_{i}$       200
$\prec$       216 283
$\Sigma$       200
$\Sigma^{*}$       3
$\sigma_{a}$       215
$\varepsilon$       2
$\varepsilon$ -rule      111
$\vDash$       123 162
$\vdash^{*}_{M}$       162
$\vdash_{M}$       162
$\vee$       62 324
$\wedge$       324
$\zeta$       200
(k, $\ell$ )-CNF      370
(k, $\ell$ )-Sat      370
2SAT      370
3DM      see "Three-Dimensional Matching"
3SAT      342
3Sat-Exactly-One      349
3Sat-Not-All      349
A*      4
A-rule      119
AB      3
Ackermann function      224
Adjacency matrix      328
Alphabet      1
Alphabet, Arabic digit      1
Alphabet, binary      1
Alphabet, Roman      1
Ambiguity      112
Approximation problem      374
Approximation ratio      374
Arden's lemma      6
ASSIGNMENT      see "Boolean function"
A\B      3
Bin Packing (BP)      364 383
Binary string      1
Boolean algebra      324
Boolean formula      325
Boolean formula, clause      342
Boolean formula, conjunctive normal form (CNF)      342
Boolean formula, disjunctive normal form (DNF)      358
Boolean formula, literal      342
Boolean formula, satisfiable      325
Boolean function      204 324
Boolean function, assignment      325
Boolean function, assignment, truth      325
Boolean function, associative law      325
Boolean function, commutative law      324
Boolean function, De Morgan's law      325
Boolean function, distributive law      325
Bottleneck Steiner Tree (BST)      380
Bounded PCP      339
Bounded Tiling      339
bp      see "Bin Packing"
BST      see "Bottleneck Steiner Tree"
Busy Beaver function      266
Busy Beaver Problem      263
Certificate      324
Changing base      220
Characteristic function      164 215
Church — Turing thesis      192
Church — Turing Thesis, extended      293
Clause      342
Clock machine      300
CNF      see "Conjunctive normal form"
CNF-Sat      342
Co-NP      336
co-r.e. set      242
Coinf      257
Complementation, of a set      3
Complete set      251 see
composition      200
Computation path      124
Computational model, reasonable      192
Concatenation, of lanugages      3
Concatenation, of strings      2
Conjunction      324
Conjunctive normal form (CNF)      342 see src='/math_tex/d30a65b936d8007addc9c789d5a7ae4982.gif'
Conjunctive normal form (CNF), nonpolar representation      369
Conjunctive normal form (CNF), polar representation      369
Connected-VC      384
Constant function      201
Context-free grammar      90
Context-free grammar, ambiguous      112 276
Context-free grammar, generating a sentence      91
Context-free grammar, left-factoring      121
Context-free grammar, leftmost graph      111
Context-free grammar, linear      158
Context-free grammar, nonterminal symbol      89
Context-free grammar, starting symbol      90
Context-free grammar, strong LL(k)      120
Context-free grammar, terminal symbol      89
Context-free language      91
Context-free language, inherently ambiguous      118
Context-sensitive grammar      314
Context-sensitive language      314
Convex partition      383
Cook's theorem      351
Crossing sequence      173 174
Cubic VC      369
De Morgan's law      325
Decision problem      243 370
Degree of unsolvability      254
Derivation      91
Derivation tree      109

Derivation, leftmost      110
Deterministic finite automata (DFA)      23
Deterministic finite automata (DFA), (state) transition function      23 25
Deterministic finite automata (DFA), accepting a language      24
Deterministic finite automata (DFA), accepting an input string      24 25
Deterministic finite automata (DFA), computation path      25
Deterministic finite automata (DFA), final state      24
Deterministic finite automata (DFA), finite control      23
Deterministic finite automata (DFA), initial state      24
Deterministic finite automata (DFA), minimum      70
Deterministic finite automata (DFA), product automata      33
Deterministic finite automata (DFA), rejecting an input string      24
Deterministic finite automata (DFA), states      23
Deterministic finite automata (DFA), tape      23
Deterministic finite automata (DFA), tape head      23
Deterministic finite automata (DFA), transition diagram      24
Deterministic Turing machine      see "Turing machine"
DFA      see "Deterministic finite automata"
DGIso      see "Digraph Isomorphism"
Diagonalization      241 242
Diagonalization, space-bounded      297
Digraph      see "Directed graph"
Digraph Isomorphism (DGIso)      341
Directed graph      16 see
Directed graph, in-edge      16
Directed graph, labeled      see "Labeled digraph"
Directed graph, out-edge      16
Disjunction      324
Disjunctive normal form (DNF)      14 358 see
DNF      see "Disjunctive normal form"
Dovetailing      234
DTM      see "Turing machine"
Dynamic programming      294
Edge coloring      385
Eight-Queen Problem      331
Elementary product      357
Elementary sum      342
EMP      248
Empty string      2
Enumeration theorem      232
Equivalence class      70
Equivalence relation      70
EUCLIDEAN TSP      383
Existential quantifier, bounded      204
Exponential functions      284
Feasible problem      294
Feasibly solvable language      294
fibonacci function      206
FIN      253
Finite automata      see "Deterministic finite automata and Nondeterministic finite automata"
FPTAS      see "Polynomial-time approximation scheme"
Fully space-constructible function      297
Fully time-constructible function      300
Function(s)      see also " Boolean function"
Function(s), Ackermann      224
Function(s), constant      201
Function(s), exponential      284
Function(s), growth rate      283
Function(s), increasing      239
Function(s), initial      200
Function(s), multi-valued      see "Multi-valued function"
Function(s), pairing      207
Function(s), partial      164
Function(s), partial recursive      see "Recursive function"
Function(s), poly-log      283
Function(s), polynomial      283
Function(s), polynomial-time computable      337 370
Function(s), polynomially honest      337
Function(s), primitive recursive      201 218
Function(s), projection      200
Function(s), recursive      215
Function(s), subexponential      283
Function(s), successor      200
Function(s), superexponential      284
Function(s), threshold      338
Function(s), total      164
Function(s), Turing-computable      164 168 171
Function(s), zero      200
Function-index set      251
G(R)      17
Gap theorem      297
GAuto      see "Graph Automorphism"
GIso      see "Graph Isomorphism"
Goedel numbering      208
Grammar      90 193
Grammar, context-free      see "Context-free grammar"
Grammar, context-sensitive      314
Grammar, left-linear      96
Grammar, linear      99
Grammar, right-linear      96
Grammar, unrestricted      193
Graph Automorphism (GAuto)      350
Graph Isomorphism (GIso)      339
Graph(s)      16 328 see
Graph(s), adjacency matrix      328
Graph(s), cubic      369
Graph(s), cycle      16
Graph(s), edge      16
Graph(s), edge-square      384
Graph(s), isomorphic      339
Graph(s), loop      16
Graph(s), path      16
Graph(s), planar      369
Graph(s), vertex      16
Graph(s), vertex cover      329
Growth rate      283
Guess-and-verify algorithm      307 323
Halting problem      243
Hamiltonian cycle      328
Hamiltonian Cycle (HC)      328
HC      see "Hamiltonian Cycle"
Hitting Set (HS)      330
Homomorphism      60
HS      see "Hitting Set"
IF-THEN-ELSE      203
Increasing function      239
Independent set      331
Independent Set (IS)      331
Index set      see "Set-index set and Function-index set"
Index(R)      70
Induced subgraph      360
Induction, mathematical      13
Inductive definition      13
inf      244
Inherent ambiguity      149
Initial functions      200
Integer factoring      334
Integer Programming (IP)      332
Intersection      3
IP      see "Integer Programming"
IS      see "Independent Set"
Isomorphic graphs      339
Isomorphism function      339
item(n)      208
k-minimum spanning tree      383
Kleene closure      4
Knapsack      363 383
Knight's Tour      328
Kolmogorov complexity      264
l'Hopital's rule      284
L(G)      91
L(M)      24 25 40
l(n)      207
l(R)      8
Labeled digraph      17 55
Labeled digraph, $\varepsilon$ -edge      18
Labeled digraph, final vertex      17
Labeled digraph, initial vertex      17
Labeled Markov algorithm (LMA)      199
Language      3

1 2 3

О проекте