Wegener I. — Complexity of Boolean Functions :: Электронная библиотека попечительского совета мехмата МГУ

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

Авторизация

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

Wegener I. — Complexity of Boolean Functions

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

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

Название: Complexity of Boolean Functions

Автор: Wegener I.

Аннотация:

Presents a large number of recent research results previously unavailable in book form. Initially deals with the wee-known computation models, and goes on to special types of circuits, parallel computers, and branching programs. Includes basic theory as well recent research findings. Each chapter includes exercises.

Язык:

Рубрика: Математика/

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

ed2k: ed2k stats

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

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

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

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

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

$\mathrm{NC}_1$ reducibility      307
$\Pi_k$ -circuit      320
$\Sigma_k$ -circuit      320
(h, k)-disjoint Boolean sum      163
(k, s) - Lupanov representation      91
1 - fan-in      326
Addition      7 39 124 313 322 341 348
Affine function      251
Ajtai, Komlos and Szemeredi sorting network      152
Almost all      87
Arithmetic circuit      64
Ashenhurst decomposition      304
Basis      7
Batcher sorting network      149
Bilinear function      169
Bipartite matching      310
Boolean convolution      58 168 209 350
Boolean matrix product      78 107 170 350
Boolean sum      36 107 163 213
bpp      286
Branching program      414
Canonical slice      203
Carry function      39 226 341
Carry save adder      51
Carry-look-ahead-adder      83
Cell partition      388
Central slice      204
Chinese remainder theorem      61
Circuit      7
Circuit size      9
Circuit value problem      310
Clause      36
Clique function      107 184 189 192 203 204 257 270 384 421 422 427 436
Clique-only function      430 438
CO WRAM      363
Communication width      363
comparison function      143 322
Complete basis      9
Conditional sum adder      40
Configuration      278
Conjunctive normal form      5
Connectivity      85 309
Constant depth reducibility      312
Counting function      74 123 127 252 314
CRCW PRAM      363
CREW PRAM      362
Critical complexity      379
data rate      348
De Morgan laws      4
Decision tree      419
Decoding circuit      90
Depth      9
Determinant      81 256 262 343 422
Direct product      301
Discrete Fourier Transform      63
Disjoint bilinear form      215
Disjunctive normal form      5
Division      67 308
Dual function      148
Elimination method      121
Elusive function      418
Equality test      126
EREW PRAM      362
Essential dependence      19 120
Eulerian cycle      309
Evasive function      418
Exactly - k - function      74 426
EXP TAPE HARD      139
Explicitly defined function      119 139
Exponential growth      17
Fan-in      11
Fan-out      10
Fast Fourier Transform      62
Fischer, Meyer and Paterson method      251
Formula      12
Formula size      12
Gate      7
Generating circuit      283
Graded set of Boolean functions      389
Graph property      402
Hamiltonian circuit      217 426
Hierarchy      296 337 394 436
Hodes and Specker method      249
Homogeneous function      107
Horner scheme      227
Implicant      24
Karnaugh diagram      30
Krapchenko method      258
Las Vegas algorithm      286
Logical level      23 320
Logical permanent      193 426
Majority function      154 243 312 313 333 426 436
Marriage problem      102

Mass production      301
Maxterm      5
Merging function      149 151 158 322
Minimal polynomial      23
Minterm      5
Monom      23
Monotone basis      145
Monotone circuit      145
Monotone disjunctive normal form      32
Monotone function      3
Monotone representation      197
Monotone storage access function      399
Monte Carlo algorithm      285
Multiplication      51 226 308 313 350
NC — Nick's class      292
Nechiporuk method      253 421
Negative envelope of convolution      58
Network flow problem      310
Non degenerated function      19 120
Non deterministic Turing machine      269
Non uniform computation model      19 279 363 414
NP      33 269
NP - completeness      33 184 203 270 288
Oblivious Turing machine      271
Odd-even merge      149
Oracle      270 307
P      269
P / Poly      283
Parity function      36 125 261 312 313 324 380 387
Partially defined function      22
Perfect matching      193 426
Period      348
Permutation branching program      434
Planar circuit      344
Polynomial      23
Polynomial growth      17
Prefix problem      48
Prime clause      36
Prime implicant      24
Probabilistic computation model      285 352
Processor partition      388
Programmable circuit      110
Projection reducibility      146 309
Pseudo complement      195
Quadratic function      107
Quine and McCluskey algorithm      25
Radix - 4 -representation      54
Random restriction      326
Read-once-only branching program      423
Replacement rule      160
Ring sum expansion      6
Root of identity      62
Satisfiability problem      270 289
Sch?onhage and Strassen algorithm      56
Selection function      20 218
Self reducibility      289
Semi-disjoint bilinear form      169
Sensitive complexity      374
Set circuit      208
Set cover problem      33
Shannon effect      88
Shannon's counting argument      87
Single level      236
SIZE      9
SIZE - DEPTH(poly;const)      312
Slice function      195
Sorting function      148 158 313
Sorting network      74 148
Space complexity      269
Stockmeyer hierarchy      270
Storage access function      76 123 374 420
Storage access function for indirect addressing      255 422
Strassen algorithm      79
Strong connectivity      310
Subtraction      50
Symmetric function      74
Synchronous circuit      340
Table of prime implicants      27
Threshold function      74 107 127 148 154 196 235 239 243 250 313 323 357 422
Time complexity      269
Trade-off      225
Transitive function      349
Turing machine      268
Uniform computation models      267 292
Universal circuit      110
Universal gate      112
Universal graph      112
Value function      176
Value vector      74
Variational Principle      106
VLSI      226 347
Weak Shannon effect      106
Width of a branching program      417
WRAM      363

О проекте