Главная Промышленная автоматика.

УКАЗАТЕЛЬ ЛЕММ, ТЕОРЕМ И АЛГОРИТМОВ

ИМЕННОЙ УКАЗАТЕЛЬ

Номер

Стр.

Номер

Стр.

Номер

Стр.

Номер

теоремы

теоремы

теоремы

теоремы

4.11

5.17

5.25

4.12

5.18

5.26

5.10

5.19

5.11

5.20

5.12

5.21

5.13

5.22

5.14

5.23

5.15

5.24

5.16

Стр.

493 497 522 529 530 531 538 555

Номер алгоритма

0.1 0.2 0.3 1.1 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9

Стр.

60 63 65 85 127 149 154 155 155 159 169 171 17!

Номер алгоритма

2.10

2.11

2.12

-2.13

2.14

2.15

2.16

Стр.

172 174 176 180 183 !87 214 250 287 326 340 353

Номер ал горнтма

4.4 4.5 4.6 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9

Стр.

356 359 367 385 390 391 396 397 399 427 437 440

Номер алгоритма

5.10

5.11

5.12

5.13

5.14

5.15

5.16

5.17

5.18

5.19

Стр.

442 444 46! 465 472 476 486 487 492 496 5)9 530

Аандераа (Aanderaa S. D.) 48 Абрахам (Abraham S.) 123 Абэ {Abe N.) 102 Агафонов В. Н. 408 Айронс (Irons Е. Т.) 96, 268, 351, 5!0 Ангер (Unger S. Н.) 351 Анисимов А. В. 408 Арбиб (Arbib М. А.) 163 Ахо (Aho А. V. ) 123, 220, 283, 408, 409, 452, 480

Барздннь Я. М. 163 Барнет (Barnet М. Р.) 268 Бар-Хиллел (Bar-Hillel Y.) 102, 123, 241

Бауэр Ф. (Bauer F. L.) 510 Бауэр X. (Bauer Н.) 480 Беккер (Becker S.) 480 Берж (Berge С.) 68 Бжозовский (Brzozowsky J. А.) 147, 163

Бирман (Birman А.) 542 Блатиер (Blattner М.) 24! Бобров (Bobrow D. G.) 102 Бородин (Borodin А.) 52 Брукер (Brooker R. А.) 96, 35! Бук (Book R. V.) 123. 241 Бут (Booth Т. L.) 163 Бэкус (Backus J. W.) 95

Вайз (Wise D. S.) 510

Вайнср (Wciner P.) 163

Валиант (Vahfinl L. G.) 372

Вальк (Walk K.) 74

Вебер (Weber H.) 480

ван Вейнгаарден (van Wijngaarden A.)

75. 559 Вегбрейт (Wegbreit B.) 75 Вельбицкий И. В. 408. 411 Виноград С. (Winograd S.) 48

Виноград Т. (Winograd Т.) 102 Вирт (Wirth N.) 480, 565 Возенкрафт (Wosencraft J. М.) Вуд (Wood D.) 408 Вудс (Woods W. А.) 102

Галлер (Galler В. А.) 74

Гилл (Gill А.) 163

Гинзбург А. (Ginzburg А,) 163

Гинзбург С. (Ginsburg S.) 123, !63,

192, 241, 268, 305 Гладкий А. В. 123, 241 Гончарова Л. И. 452 Глушков В. М. 163 Готлиб (Gotlieb С. С.) 352 Грин (Green М. W.) 96 Грейбах (Greibach S.) 123, 192, 241, 305 Грис (Gries D.) 95, 96 Грисволд (Griswold R. Е.) 562 Гриффите (Griffiths Т. V.) 268, 35! Гросс (Gross М.) 24! Грэй (Gray J. N.) 220, 315, 480, 510, 558 Грэхем Р. (Graham R. М.) 510 Грэхем С. (Graham S. L.) 372, 480

Дениинг (Denning Р. J.) 480 Де Ремер (De Remer F. L.) 452, 569 Джентльмен (Gentleman W. M.) 77 Джонсон В. (.lohnson W. L.) 295 Джонсон С. (Johnson S. C. ) 408, 409 Дейкстра (Dijkstra E. W.) 98 Домёлкн (Domolki B.) 352 Дьюар (Dewar R. B. K.) 96 Дэвис (DavisM.) 51, 52

Замельсон (Samelson K-) 510 Зыков A. A. 68 Зонис в. С. 452



Ибарра (Ibarra О.) 220 Ингерман {Ingerman Р. Z.) 96 Ихбна {ichbia J. D.) 480

Кантор (Cantor D. G.) 24!

Камеда {Kameda Т.) 163

Касами (Kasami Т.) 372

Кауфман В. Ш. 408, 409

Клини (Kleene S. С.) 38, 52, 147

Кнут (Knuth D. Е.) 52, 68, 74, 408,

452 542 Кок (Соске J.) 95, 96, 372 Ксшмерауэр (Colmerauer А.) 558 Комор (Komor Т.) 408, 409 Конвэй М. (Conway М. Е.) 408, 414 Коивэй Р. (Conway R. W.) 96 Кореньяк (Korenjak А. J.) 408, 452 Косараю (Kosarju S. R.) 163 Коэн Д. (Cohen D. J.) 352 Коэн Р. (Cohen R. S.) 558 Кравчик" (Krawczyk Т.) 408 Кук (Cook S. А.) 48, 220 Криетеисен (Christensen С.) 75 Куно (Кппо S.) 351 Курки-Суоиио (Kurki-Suonio R.) 408

Лавров С. С. 558 Лалонд (Lalonde W. R. ) 504 Лантен (Lentin А.) 241 Левит (Levitt К- N.) 96 Лейниус (Leinius R. Р.) 452, 480 Ли Дж. (Lee J. А. N.) 96 Ли Э. (Lec Е. S.) 504 Лнвенворт (Leavenworth В. М.) 74, 559

Локс (Loecks J.) 510

Ломет (Lomet D.) 417

Лукасевич (Lukasiewicz J.) 244

Лукаш (Lucas P.) 74

Льюис (Lewis P. M. 1!) 220, 268, 408

Мак-Илрой (Mcllroy M. D.) 74, 77 Мак-Каллок (McCullough W. S.) 123 Мак-Карти (McCarthy J.) 96 Мак-Киман (МсКееман "W- M. ) 96, 480, 510

Мак-Клюр {McClure R. M.) 96,542 Мак-Нотои (McNaughton R.) 147 Максвелл (Maxwell W. L.) 96 Мальцев A. И. 43, 46, 52 Марков A. A. 42 Мендельсон (Mendelson E.) 38 Миллер В. (Miller "W. F.) 102 Миллер Г. (Miller G. A.) 147

Минский (Minsky M.) 43, 52, 122, 163 Мицумото (Mizumoto M.) 102 Монтанари (Montanari U. G.) 102 Моргай (Morgan H. L.) 96, 296 Морзе (Morse S. P.) 480 Моррис (Morris D.) 96, 351 Моултон (Moulton P. G.) 96 Мунро (Munro I.) 68 Myp (Moor E. F.) 123, 162 Мюллер (Muller M. E.) 96

Hayp (Naur P.) 74, 559 Непомнящая A. UI. 408 Никитчснко H. C. 408 Нийхольт (Nijholt A.) 408

Огден (Ogden W.) Ордян A. A. 558 Ope (Ore 0.) 68

Павлидис {Pavlidis T.) 102 Парик (Parikh R.J.) 24! Паул (Paull M. C.) 192 Пейитер (Painter J. A.) 96 Перлз (Perles M.) 241 Перлис (PerlisA. J.) 74 Петрик (Petrick S. R.) 35! Петроне (Petrone L.) 268 Питтс (Pitts E.) 123 Пол (Paul M.) 510 Полонский {Polonsky I. P.) 562 Портер {Porter J. H.) 295 Пост (Post E. L.) 42. 52 Поудж (Poage J. F.) 562 Пратер (Prather R. E.) 163 Пфальц (Pfaltz J. L.) 98, 102 Пэр (Pair C.) 480

Рабин (Rabin M. 0.) 123, 147, 162 Райе (Rice H. G.) 192 Рассел (Russel L. J.) 96 Редько В. H. 147, 408 Рейнольде (Reynolds J. C.)96, 315, 35! Реиделл (Randell B.) 96 Роберте (Roberts P. S.) 352 Роджерс (Rogers H.) 46 Розен (Rosen S.) 95, 351 Розенкранц (Rosenkrantz D. J.) 123, 192, 408

Розенфельд (Rosenfeld A.) 98, 102 Росс (Ross D. T.) 295 Роудз {Rhodes E. M.) 480 Руццо (Ruzzo W. L.) 372

Саломаа (Salomaa A.) 147, 163, 241

Саммет {Sammet J. E,) 42, 74

Скотт (Scott D.) 123, 147, 162

Стил (Steel T. B.) 74

Стирнз {Stearns R. E.) 220, 241, 268, 408

Стэндиш (Standish T.) 96

Cynnec {Suppes P.) 13

Сэттли (Satlley K.) 351

Танака (Tanaka K.) 102

Тоёда (Tojoda J.) 102

Томпсон (Thompson K-) 163, 296

Тории (Torii K.) 372

Трахтенброт Б. A. 163

Трахтенгерц Э. A. 510

Трубчанинов Г. Г. 510

Тьюринг (Turing А. М.) 42, 43, 51, 123

Уллиан {Ullian J. S.) 241

Ульман (Ullman J. D.) 52, 123, 220,

241, 283, 408, 409, 452, 480, 542 Уолтере {Walters D. A.) 452 Уорли (Worley W. S.) 96 Уортмэи (Wortman D. B.) 96, 510 Уорщолл (Warshall S.) 68, 96

Фельдман (Feldman J; A.) 95, 96, 499, 510

Фишер M. {Fischer M. J.) 123, 480

Фишер П. {Fischer P. C.) 52

Флойд (Floyd R. W.) 68, 96, 192, 241,

351, 480, 510 Фостер (Foster J. M.) 408 Фримэн (Freeman D. N.) 96, 296 Фу (Fu K. S.) 102 Фуксман A. Л. 408, 409 Футрель (Futrelle R. P.) 268

Хавел (Havel I. M.) 510

Халмош {Halmos P." R.) 13, 38

Хант (Hunt H. B.) 452

Харари (Harary F.) 68

Харрисон (Harrison M. A.) 163, 220,

315, 372, 510, 558 Хартманис (Hartmanis J.) 52, 147, 220 Хаскел (Hackell R.) 315 Хафмен (Huffman D. A.) 162 Хейнс (Haines L. H.) 123

Хейс {Hays D. G.) 372

Хекст {Hext J. B.) 352

Хомский (Chomsky N.) 42, 74, 102,

123, 147, 192, 220, 24! Хопгуд (Hopgood F. R. A.) 96, 510 Хопкрофт {Hopcroft J.E.) 52, 123,

163, 220, 241, 408, 452 Хориииг (Horning J.J.) 96, 504, 510 Хохшнруиг {Hochsprung R. R.) 96

Цейтин Г. С. 102

Чёрч (Church А.) 38, 42, 43 Читэм (Cheartham Т. Е.) 74, 96, 315, 35!

Чулнк I (Culik К-) 268

Чулнк II (СнИк К- И) 408, 558

Шамир (Shamir Е.) 24! Шапиро (Shapiro R. М.) 96 Шварц (Schwartz J. Т.) 95, 96 Шевченко В. В. 408 Шепердсон (Shepherdson J. С.) 147 Шимаиский (Szymansky Т. G.) 452 Шкильняк С С. 408 Шорре (Schorre D. Uv) 96, 351, 542 Шоу (Shaw А. С.) 98, 102 Штрассен (Strassen V.) 48, 68 Шумей А. С. 452, 510 Шютценберже (Schutzcnberger М. Р.) 192, 220, 24!

Эваис (Evans А. Jr.) 510, 569 Эви (Evey R. J.) 192, 220 Эйкель (Eickel J.) 510 Экли (Ackiey S. I.) 295 Элспас (Elspas В.) 96 Эигелер (Engeler E.) 74 Эрлаид (Ireland M. !.) 52 Эрли (Earley J.) 372 Эттингер (Oettinger A.) 220, 35!

Юнеико E. Л. 408,-41!

Яжабек (Jarzabek S.) 408 Ямада (Yamada) H.) 147 Янгер (Younger D. H.) 372



ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ

Аванцепочка (lookahead string) 378 , 427 см. также Заглядывание вперед Автомат (autornaton) см. также Распознаватель, Преобразователь

- конечный (finite) 138, !47-151, 286-293, 449 --двусторонний (two-way) 146

--детерминированный (deterministic) 138, 287

--недетерминированный (nondeterministic) 135, 287-293

--полиостью определенный (completely specified) 135

--приведенный (reduced) 148-151

- линейно ограниченный (linear bounded) 120

- с магазинной памятью (pushdown) 114, 193-220, 318 --двусторонний (two-way) 219, 220

--детерминированный (deterministic) 211-220, 228, 229, 237-240, 283 384.

450, 501, 503, 522-525

---дочитывающий (continuing) 215, 216

---пез а цикли Бающийся (halting) 318

--расширенный (extended) 199-201, 212

--с одним поворотом (one-turn) 237

Алгебра булева (Boolean algebra) 36, J53

Алгол (ALGOL) 74, 75, 226, 227, 264, 287, 347, 408, 559

Алгоритм (algorithm) 38-51

- всюду определенный 40

- Домёлки (Domolkis) 351, 352, 507, 510

- Кока - Янгера - Касами (Соске - Younger - Kasami) 352-358

- Маркова 42

- недетерминированный (nondeterministic) 320, 346, 347, 351

- разбора, 1]редсказывающий (predictive parsing) 205, 378-381, 391,-395, 408 --корректный (valid) 380

- Уоршолла (WarshaUs) 63, 68

- частичный (procedure) 38-5!

- Эрли (Earleys) 358-372, 450 Алфавит (alphabet) 27

- входной (input) см. Символ входной

- выходной (output) см. Символ выходной

- состояний (of states) см. Состояние Альтернатива (нетерминала) (alternate) 32! Анализ (analysis)

- лексический (Jexfcal) 76-79, 283-296

--непрямой (indirect) 78, 286-290

--прямой (direct) 78, 290-293

- синтаксический (syntactic) см. Разбор

Анализатор (parser) см. также Анализ

- двухмагазинный (two-stack) 544-547, 556-558

- канонический LR(/i) (canonical LR(k)} 444-447

- левый (left) 299-301

- tio левому участку (left-corner) 348-350

- правый (right) 302-304. 338

- предсказывающий (predictive) см. Алгоритм разбора, предсказывающий Л-правило (-4-production) 175

Блок-схема (flowchart, d-chart) 98-!0!

Веер (в дереве) см. Куст (в дереве) Вершина (графа) (node, vertex) 52

- концевая см. Лист

Включение (множеств) (inclusion) 13, 238 Вход (input) 38 см. также Лента входная Вывод (derivation) 107, 118

- левый (leftmost) 167, 168, 232, 233, 297, 356, 357

- правый (rightmost) 167, 168,297 Выражение (expression)

- арифметическое (arithmetic) 72, 73, 108, 245, 253

- инфиксное (infix) 244

- постфиксное (postfix) 244, 245. 247, 248, 259, 264, 267, 529

- префиксное (prefix) 244 , 245 , 259, 264, 267

- расширенное регулярное (extended regular) 284-290

- регулярное (regular) 124-131, 145, 147 Высота (всошины дерева) (height) 58, 84 Выход (output) 38. 243, 255, 258

Генерация кода (code generation) 75, 82-88, 90, 92, 93 Глубина (вершины дерева) (depth) 58 Головка входная (распознавателя) (input head) ИЗ-115 Гомоморфизм (homomorphism) 29, 225, 236, 238, 239, 243, 244 Грамматика (grammar) 105

- автоматная см. Грамматика регулярная

- без е-правил (еЛтее) 172, 173, 314, 340, 343, 346, 376, 402, 450, 478, 492

•- без ограничений (unrestricted) см. Грамматика общего вида без циклов (сус1< free) 175, 314, 340, 343, 346, 367

- бсскоптекстнап см. Грамматика контекстно-свободная

- входная (СУ-схемы) (input underlying) 250

- выходная (output) 250

- индексная (indexed) 120, 121

- Колмерауэра (Colmerauer) 549, 554-558

- контекстно-зависимая (context-sensitive) 111, !12, 117, 119, 12!, 237, 452

- контекстно-свободная (context-free) 111, 112, 117, 119, 121, 237

- левоаналнзируемая (left parsable) 304-306, 381

- леволинейная (left linear) 145

- леворекурсивная (left recursive) 178-181, 324, 325, 33!, 332, 385. 400

- линейная (linear) 191, 237, 268

- Щк) 402-408

- LL 376

- LL{k) 301, 373-408, 449, 450

- LL(1) 373, 382-387, 408, 411. 539





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 [98] 99 100 101

0.0019