| Title:
|
Минимизация конечных автоматов (Russian) |
| Title:
|
Minimization of finite automata (English) |
| Title:
|
Minimalizace konečných automatů (Czech) |
| Author:
|
Šiškov, D. B. |
| Language:
|
Russian |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
8 |
| Issue:
|
4 |
| Year:
|
1972 |
| Pages:
|
(297)-316 |
| Summary lang:
|
Czech |
| . |
| Category:
|
math |
| . |
| MSC:
|
68Q45 |
| MSC:
|
94A30 |
| idZBL:
|
Zbl 0243.94043 |
| idMR:
|
MR0329802 |
| . |
| Date available:
|
2009-09-24T16:26:22Z |
| Last updated:
|
2012-06-04 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/124390 |
| . |
| Reference:
|
[1] В. М. Глушков: Синтез цифровых автоматов.Физматгиз, Москва 1962. Zbl 1005.68507 |
| Reference:
|
[2] Н. Е. Кобринский Б. А. Трахтенброт: Введение в теорию конечных автоматов.Физматгиз, Москва 1962. Zbl 1226.30001 |
| Reference:
|
[3] Ю. И. Янов: О тождественных преобразованиях регулярных выражений.Доклады АН СССР 147 (1962), 2, 327-330. Zbl 1005.68507, MR 0142460 |
| Reference:
|
[4] C. D. Popovici: Itilizarea grafurilor pentru obţinirea schemei cu un unmăr minim de relee.Studii şi cercetări mat. Acad. RPR (1962), 4, 553-563. |
| Reference:
|
[5] В. М. Глушков: О минимизации микропрограмм.Известия АН СССР, Техническая кибернетика (1964), 1, 3-8. Zbl 1117.65300 |
| Reference:
|
[6] Л. В. Мацевитий: Алгоритм минимизации схем микропрограмм.Известия АН СССР, Техническая кибернетика (1964), 1, 9-19. Zbl 1117.65300 |
| Reference:
|
[7] В. Г. Лазарев: Матричный метод минимизации схем микропрограмм.Известия АН СССР, Техническая кибернетика (1965), 2, 35-42. Zbl 1099.01519 |
| Reference:
|
[8] В. М. Глушков: Теория автоматов и формальные преобразования микропрограмм.Кибернетика (1965), 5, 1-10. Zbl 1099.01519 |
| Reference:
|
[9] В. М. Глушков: К вопросу о минимизации микропрограмм и схем алгоритмов.Кибернетика (1966), 5, 1-4. Zbl 1155.78304, MR 0226298 |
| Reference:
|
[10] Т. Я. Бучма В. И. Карташев: Автоматизация получения наилучшего объединения микропрограммных автоматов.Теория дискретных автоматов. Зинатне, Рига 1967, 55-62. Zbl 1230.82006 |
| Reference:
|
[11] В. П. Кутепов: О тождественных преобразованиях регулярных выражений.Цифровая вычислительная техника и программирование, вып. 2. Советское радио, Москва 1967, 138-143. Zbl 1103.35360 |
| Reference:
|
[12] Gr. C. Moisil: Theorie structurelle des automates finis.Gauthier-Villars, Paris 1967. Zbl 0168.26004 |
| Reference:
|
[13] I. M. Havel: The Theory of Regular Events I.Kybernetika 5 (1969), 5, 400-419. Zbl 0181.31102, MR 0256787 |
| Reference:
|
[14] I. M. Havel: The Theory of Regular Events II.Kybernetika 5 (1969), 6, 520-544. Zbl 0184.28703, MR 0256787 |
| Reference:
|
[15] Ч. А. Аскеров Ф. И. Пепинов: Объединение операторов в логических схемах алгоритмов.Управление сетями связи и синтез управляющих устройств. Наука, Москв 1969, 34-41. Zbl 1231.90028 |
| Reference:
|
[16] В. А. Горбатов: Синтез микропрограммых автоматов по временным диаграммам из функционирования.Цифровая вычислительная техника и программование, вып. 5. Советское радио, Москва 1969, 192-202. Zbl 1149.62317 |
| Reference:
|
[17] Л. А. Кузнецов В. Л. Патрикеев: Минимизация матричных схем Янова.Кибернетика (Луганск. отд.), Тр. семинара, вып. 2, Киев 1969, 59-65. Zbl 1231.90028 |
| Reference:
|
[18] В. Л. Патрикеев: Минимизация операторных схем Янова.Техническая кибернетика, вып. 6, Киев 1970, 72-81. Zbl 1170.92319 |
| Reference:
|
[19] В. В. Сапожников, Вл. В. Сапожников: О преобразовании первичной таблицы переходов.Автоматика и телемеханика (1970), 5, 204-206. Zbl 1170.92319 |
| Reference:
|
[20] В. Н. Гребенщиков: Комбинированный метод синтеза конечных автоматов.Изв. высш. учебн. заведений, Радиофизика 13 (1970), 11, 1736-1740. Zbl 1170.92319 |
| Reference:
|
[21] J. Hartmanis R. E. Stearns: Some Dangers in State Reduction of Sequential Machines.Information and Control 5 (1962), 4, 252-260. MR 0151375 |
| Reference:
|
[22] D. A. Huffmann: The Synthesis of Sequential Switching Circuits.J. Frank. Inst., 257 (1954), 3, 4, 161-190, 275-303. MR 0062648 |
| Reference:
|
[23] G. H. Mealy: A Method for Synthesising Sequential Machines.B.S.T.J. 34 (1955), 5, 1045-1079. MR 0073450 |
| Reference:
|
[24] D. D. Aufenkamp F. E. Hohn: Analysis of Sequential Machines.IRE Trans. Electr. Comput. 6 (1957), 6, 276-283. MR 0093934 |
| Reference:
|
[25] D. D. Aufenkamp: Analysis of Sequential Machines.IRE Trans. Electr. Comput. 7 (1958), 2, 299-306. |
| Reference:
|
[26] M. Phister: Logical Design of Digital Computers.John Willey and Sons, New York 1958. Zbl 0090.10601, MR 0093930 |
| Reference:
|
[27] A. Gill: Introduction to the Theory of Finite State Machines.McGraw-Hill Book Comp., Inc., New York 1962. Zbl 0158.25801, MR 0209083 |
| Reference:
|
[28] S. Ginsburg: An Introduction to Mathematical Machine Theory.Reading Mass. Addison-Wesley 1962. Zbl 0102.33804, MR 0145693 |
| Reference:
|
[29] В. Г. Лазарев Е. И. Пийль: Уменышение числа состояний одного класса конечных автоматов.Доклады AH CCCP 143 (1962), 5, 1064-1066. Zbl 1226.30001 |
| Reference:
|
[30] A. Železnikar: Ekvivalentnost i minimizacija apstraktnih automata.Automatika (1965), 2, 3, 133-141. |
| Reference:
|
[31] P. E. Wood: Switching Theory.McGraw Hill, New York 1968. Zbl 0176.28202 |
| Reference:
|
[32] E. J. McCluskey: Minimum State Sequential Circuits for a Restricted Class of Incompletely Specified Flow Tables.B.S.T.J., 41 (1962), 6, 1759-1768. |
| Reference:
|
[33] S. Ginsburg: A Technique for the Reduction of a Given Machine to a Minimal State Machine.IRE Trans. Electr. Comput. 8 (1959), 3, 384-391. |
| Reference:
|
[34] M. C. Paul S. H. Unger: Minimizing the Number of States in Incompletely Specified Sequential Switching Functions.IRE Trans. Electr. Comput. 3 (1959), 8, 356-367. |
| Reference:
|
[35] R. Narasimhan: Comments on Paper: Minimizing Incompletely Specified Sequential Switching Functions.by M. C. Paul and S. H. Unger. IRE Trans. Electr. Comput. 10 (1961), 3, 531-532. |
| Reference:
|
[36] A. Grasselli: Minimal Closed Partitions for Incompletely Specified Sequential Machines.Electron-Letters (1962), 2, 191-194. |
| Reference:
|
[37] B. Г. Лазарев Е. И. Пийль: Синтез асинхронных конечных автоматов.Наука, Москва 1964. Zbl 1230.62001 |
| Reference:
|
[38] A. Grasselli F. Luccio: A Method for Minimizing the Number of Internal States in Incompletely Specified Sequential Networks.IEEE Trans. Electr. Comput. 14 (1965), 3, 350-359. |
| Reference:
|
[39] В. И. Трошин: Алгебраический способ минимизации неполностью определенных последователъностных машин.Автоматика и телемеханика 26 (1965), 2, 2176-2181. Zbl 1099.01519 |
| Reference:
|
[40] J. С. Beatty: On some Properties of the Semigroup of a Machine which Are Preserved under State Minimization.Inform. and Control 11 (1967), 3, 290-316. Zbl 0157.02101, MR 0243940 |
| Reference:
|
[41] A. Grasselli F. Luccio: Une methode de minimalisation du nombre des états internes des réseaux séquentiels incomplétement spécifiés.Algèbre de Boole et machines logiques. Dunod, Paris 1967. |
| Reference:
|
[42] J. Gruel: Ein Beitrag zum Thema "Minimalautomaten".Wiss. Z. Techn. Univ. Dresden (1968), 5, 1109-1112. Zbl 0172.20801, MR 0242588 |
| Reference:
|
[43] А. Грасселли Ф. Лучио: Метод совместной минимизации строк и столбцов таблицы переходов.Автоматика и телемеханика (1968), 8, 100-115. Zbl 1236.41005 |
| Reference:
|
[44] A. Schmitt: Zur Theorie der nichtdeterministischen und unvollstandigen Automaten.Computing 4 (1969), 1, 56-74. MR 0246723 |
| Reference:
|
[45] S. С. De Sarcar A. K. Basu A. K. Chondhury: Simplification of Incompletely Specified Flow Tables with the Help of Prime Closed Sets.IEEE Trans. Comput. 18, (1969), 10, 953-956. |
| Reference:
|
[46] I. Muntean: Sinteza automatelor finite cu numer minim de stări.Studii şi cercetărimat. Acad. R.S.R. 20 (1968), 1, 3-13. MR 0253826 |
| Reference:
|
[47] A. Bouchet: An Algebraic Method for Minimizing the Number of States in an Incomplete Sequential Machine.IEEE Trans. Comput. 17 (1968), 8, 795-798. Zbl 0169.31501, MR 0235913 |
| Reference:
|
[48] U. Isphording: Ein Matrizenalgorithmus zur Minimizierzung der Schalteranzahl in Schalternetzwerken.Arch. elek. Übertrag. 24 (1970), 3, 132-138. MR 0307827 |
| Reference:
|
[49] J. Kella: State Minimization of Incompletely Specified Sequential Machines.IEEE Trans. Comput. 19 (1970), 4, 342-348. Zbl 0222.94051, MR 0457005 |
| Reference:
|
[50] T. Kameda P. Weiner: On the State Minimization of Nondeterministic Finite Automata.IEEE Trans. Comput. 19 (1970), 17, 617-627. MR 0398705 |
| Reference:
|
[51] Z. Kohavi: Reduction of the Number of States in Incompletely Specified Sequential Machines.Electron. Letters (1965), 7, 712-715. |
| Reference:
|
[52] Ю. В. Потосин E. А. Бутаков: Минимизация числа сотсояний последовательностного автомата.Труды Сибирского физико-технического института при Томском государственном университете им. В. В. Куйбышева, вып. 48 (1966), 165-180. Zbl 1230.03072 |
| Reference:
|
[53] P. Hummitzsch: Zur Reduction von partiellen Automaten mit Eingangbeschrankungen.Messen-Steuern-Regeln (1968), 4, 124-129. |
| Reference:
|
[54] Ю. В. Потосин: Экспериментальная оценка одного метода минимизации числа cостояний дискретного автомата.Сб. „Проблемы синтеза цифровых автоматов". Наука, Москва 1967, 101-107. Zbl 0302.40008 |
| Reference:
|
[55] В. П. Диденко: О методах минимизации и построении мостиковых структур релейных устройств.Автомат. регулирование и управление. АН СССР, Москва 1962, 444-460. Zbl 1005.68507 |
| Reference:
|
[56] Э. Дж. Мак-Класки: Многократные схемы с минимальным числом состояний для ограниченного класса неполностью определенных таблиц переходов.Теория конечных и вероятностных автоматов. Наука, Москва 1965, 362-371. Zbl 1099.01519 |
| Reference:
|
[57] В. Г. Лазарев: Матричный метод минимизации схем микропрограмм.Известия АН СССР, Техническая кибернетика (1965), 2, 35-42. Zbl 1099.01519 |
| Reference:
|
[58] А. А. Летичевский: О минимизации конечных автоматов.Кибернетика (1966), 1, 20-24. Zbl 1155.78304 |
| Reference:
|
[59] О. В. Медведев: Минимизация числа состояний последовательностной машины при входных последовательностях, не содержащих двух одинаковых символов подряд.Автоматика и телемеханика (1966), 5, 117-124. Zbl 1155.78304 |
| Reference:
|
[60] Э. А. Якубайтис А. Ю. Гобземис В. Г. Горбец Г. Ф. Фринцович: Минимизация объема памяти последовательностных логических схем.Автоматика и вычислительная техника, 12. Зинатне, Рига 1966. Zbl 1230.03072 |
| Reference:
|
[61] М. С. Раul G. А. Waldbaum: A Note on State Minimization of Asynchronous Sequential Functions.IEEE Trans. Electr. Comput. 16 (1967), 1, 94-97. |
| Reference:
|
[62] М. А. Спивак: К минимизации автоматов Мура.Кибернетика (1967), 1, 5-6. Zbl 1103.35360 |
| Reference:
|
[63] А. Ю. Гобземис: Минимизация числа промежуточных переменных при синтезе последовательностных асинхронных логических схем.Теория дискретных автоматов. Зинатне, Рига 1967. Zbl 1103.35360 |
| Reference:
|
[64] Г. Ф. Фринцович: Способ задания и распознавания эквивалентных устойчивых состояний последовательностных асинхронных логических схем.(ПАЛС). Теория дискретных автоматов. Зинатне, Рига 1967, 141-156. Zbl 1103.35360 |
| Reference:
|
[65] Б. Г. Миркин: Минимизация последовательностных машин относительно регулярных, полных справа событий.Автоматика и телемеханика 11, (1967), 149-153. Zbl 1103.35360, MR 0235922 |
| Reference:
|
[66] Н. J. Zander: Zur Zustandsreduction ungetakteter (asynchroner) Folgeschaltungen.Elektron. Informationsverarb. und Kybernetik, 4 (1968), 4-5, 257-277, 285-300. |
| Reference:
|
[67] W. S. Brainerd: The Minimalization of Free Automata.Information and Control 13 (1968), 5, 484-491. MR 0237236 |
| Reference:
|
[68] С. dе Renna e Sonza: A Theorem on the Reduction of Synthesized Stochastic Machines.IEEE Trans. Comput. 18 (1969), 5, 473-474. |
| Reference:
|
[69] Е. А. Гурвиц: Синтез полисинхронных дискретных устройств.Связь, Москва 1969. Zbl 1149.62317 |
| Reference:
|
[70] Д. Е. Черный: Алгебраические свойства частичных автоматов.Известия высш. учебн. заведений, Математика (1970), 2, 94-99. Zbl 1170.92319 |
| Reference:
|
[71] Г. Ф. Фринцович: Минимизация числа состояний частично определенных асинхронных конечных автоматов.Автоматика и вычислительная техника (1970), 4, 1-7. Zbl 1170.92319 |
| Reference:
|
[72] В. Т. Бардачевский В. М. Голованевский: Минимизация структурных схем конечных цифровых автоматов, построенных на феррит-транзисторных элементах.Отбор и передача информации, Респ. межвед. сб., вып. 25 (1970), 113-117. Zbl 1230.76053 |
| Reference:
|
[73] W. Stucky H. Walter: Minimal Linear Realization of Autonomous Automata.Information and Control 16 (1970), 1, 66-84. MR 0282758 |
| Reference:
|
[74] R. Hartenstein: Suchlistenstrukturen zur Darstellung gerichteter Graphen und deren Anwendung bei Synthese und Minimizierung spezieller endlicher Automaten.Elektr. Rechenanlagen (1970), 4, 208-216. |
| Reference:
|
[75] А. Д. Закревский: Синтез последовательностных автоматов и его программирование.Применение вычислительной техники для автоматизации производства. Машгиз, Москва 1961, 525-534. Zbl 1160.68305 |
| Reference:
|
[76] W. Händler: Zur praktischen Durchführung von Reductionverfahren für Schaltwerke nach Paul, Unger und Ginsburg.Z. Colloq. Schaltkreis- und Schaltwerk- Theorie, 1961, Saarbrücken, Vortragauszüge, Basel - Studgard 1963, 107-128. |
| Reference:
|
[77] А. Д. Закревский: К синтезу последовательностных автоматов.Труды Сибирскогo физико-технического института, вып. 40 (1961), 89-94. Zbl 1160.68305 |
| Reference:
|
[78] Е. А. Бутаков А. Д. Закревский: Минимизации числа осстояний релейной схемы на универсальной цифровой вычислительной машине ,,Урал".Проблемы передачи информации, вып. 11. Наука, Москва 1962. |
| Reference:
|
[79] В. М. Глушков А. А. Летичевский А. А. Стогный: Алгоритмическая система для автоматизации синтеза цифровых автоматов.Синтез релейных структур, Москва 1965, 342-344. Zbl 1225.00032 |
| Reference:
|
[80] Ю. В. Потосин: Алгоритмы минимизации числа состояний дискретного автомата.Логический язык для представления алгоритмов синтеза релейных устройств. Наука, Москва 1966, 301-325. Zbl 1155.78304 |
| Reference:
|
[81] Ю. В. Потосин: К минимизации числа состояний дискретного автомата.Тезисы докладов Всесоюзного коллоквиума по автоматизации синтеза дискретных вычислительных устройств. Новосибирск 1966, 61-63. Zbl 1155.78304 |
| Reference:
|
[82] W. Händler: Zur Theorie endlicher Automaten.Computer 1 (1966), 173-181. |
| Reference:
|
[83] Ю. В. Потосин: Экспериментальная оценка одного метода минимизации числа состояний дискретного автомата.Проблемы синтеза цифровых автоматов. Наука, Москва 1967, 101-107. Zbl 1103.35360 |
| Reference:
|
[84] I. Tomescu: Asupra problemei sintezei automatelor secvenţiale de tipul Mealy.Studii si cercetări mat. Acad. R.S.R. (1968), 5, 763-770. MR 0258542 |
| Reference:
|
[85] S. Ginsburg: On the Reduction of Superfluous States in a Sequential Machine.J.A.C.M. 6 (1959), 1, 252-282. Zbl 0088.34501, MR 0129095 |
| Reference:
|
[86] E. J. McCluskey: Minimization of Boolean Functions.B.S.T.J. 35 (1956), 6, 1236-1249. MR 0082876 |
| Reference:
|
[87] S. H. Unger: Flow Table Simplification Some Useful Aids.IEEE Trans. Electr. Comput. 14 (1965), 3, 472-475. Zbl 0235.94031 |
| Reference:
|
[88] В. Ф. Дьяченко В. Г. Лазарев Г. Г. Саввин: Управление на сетях связи.Наука, Москва 1967. Zbl 1230.82006 |
| Reference:
|
[89] W. F. Djatschenko W. G. Lasarew: Unformung logischer Algorithmenschemata und Vereinfachung der Struktur von Mikroprogramm-Automaten.Elektron. Informations-verarbeit. und Kybernetik 3 (1968), 4, 173-186. MR 0263567 |
| Reference:
|
[90] В. Г. Лазарев В. М. Ченцов: О минимизации числа внутренних состояний стохастического автомата.Синтез дискретных автоматов и управляющих устройств. Наука, Москва 1968, 150-159. Zbl 1236.41005 |
| Reference:
|
[91] A. Graselli U. Montanari: On the Minimization of READY-ONLY Memories in Microprogrammed Digital Computers.IEEE Trans. Comput 19 (1970), 11, 1111-1114. |
| Reference:
|
[92] A. S. Meisel: A Note on Internal State Minimization in Incompletely Specified Sequential Networks.IEEE Trans. Electr. Comput. 16 (1967), 4, 508-509. |
| Reference:
|
[93] М. А. Гаврилов: Проблемы поиска минимальных решений при синтезе структуры релейных устройств.Труды III Всесоюзного совещания по автоматическому управлению (техн. кибернетике). Самонастраивающиеся системы. Распознавание образцов. Релейные устройства и конечные автоматы. Наука, Москва 1967, 289-303. Zbl 1103.35360 |
| Reference:
|
[94]
: Техническая кибернетика, Проблемы управления и информации.Вопросы советской науки. Наука, Москва 1966. Zbl 1155.78304 |
| Reference:
|
[95] J. Hartmanis: Loop-free Structure of Sequential Machines.Information and Control 5 (1962), 2, 25-43. Zbl 0163.14304, MR 0144794 |
| Reference:
|
[96] E. H. Faar: Lattice Properties of Sequential Machines.J.A.C.M. (1963), 3, 365-385. MR 0156491 |
| Reference:
|
[97] G. B. Gerace G. Gestri: State Assignment for Reducing the Number of Delay Elements in Sequential Machines.Information and Control 10 (1967), 3, 223-253. |
| Reference:
|
[98] Е. Н. Вавилов Д. Б. Шишков: Об одном методе экономичного кодирования автоматов.Известия АН СССР, Техническая кибернетика (1967), 2, 104-113. Zbl 1230.82006 |
| Reference:
|
[99] М. А. Айзерман Л. А. Гусев Л. И. Розоноэр И. М. Смирнова А. А. Таль: Логика, автоматы, алгоритмы.Физматгиз, Москва 1963. Zbl 1214.14039 |
| Reference:
|
[100] Д. Б. Шишков: Декомпозиция автоматов в виде иерархических и каскадных структур.Доклады Болгарской академии наук 1 (1968), 21, 27-29. Zbl 1099.01025 |
| . |
