Минимизация конечных автоматов

Šiškov, D. B.

Kybernetika, Tome 8 (1972) no. 4, pp. 297-316

Détail

Classification : 68Q45, 94A30

Bibliographie

[1] В. М. Глушков: Синтез цифровых автоматов. Физматгиз, Москва 1962. | Zbl

[2] Н. Е. Кобринский Б. А. Трахтенброт: Введение в теорию конечных автоматов. Физматгиз, Москва 1962. | Zbl

[3] Ю. И. Янов: О тождественных преобразованиях регулярных выражений. Доклады АН СССР 147 (1962), 2, 327-330. | MR | Zbl

[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.

[5] В. М. Глушков: О минимизации микропрограмм. Известия АН СССР, Техническая кибернетика (1964), 1, 3-8. | Zbl

[6] Л. В. Мацевитий: Алгоритм минимизации схем микропрограмм. Известия АН СССР, Техническая кибернетика (1964), 1, 9-19. | Zbl

[7] В. Г. Лазарев: Матричный метод минимизации схем микропрограмм. Известия АН СССР, Техническая кибернетика (1965), 2, 35-42. | Zbl

[8] В. М. Глушков: Теория автоматов и формальные преобразования микропрограмм. Кибернетика (1965), 5, 1-10. | Zbl

[9] В. М. Глушков: К вопросу о минимизации микропрограмм и схем алгоритмов. Кибернетика (1966), 5, 1-4. | MR | Zbl

[10] Т. Я. Бучма В. И. Карташев: Автоматизация получения наилучшего объединения микропрограммных автоматов. Теория дискретных автоматов. Зинатне, Рига 1967, 55-62. | Zbl

[11] В. П. Кутепов: О тождественных преобразованиях регулярных выражений. Цифровая вычислительная техника и программирование, вып. 2. Советское радио, Москва 1967, 138-143. | Zbl

[12] Gr. C. Moisil: Theorie structurelle des automates finis. Gauthier-Villars, Paris 1967. | Zbl

[13] I. M. Havel: The Theory of Regular Events I. Kybernetika 5 (1969), 5, 400-419. | MR | Zbl

[14] I. M. Havel: The Theory of Regular Events II. Kybernetika 5 (1969), 6, 520-544. | MR | Zbl

[15] Ч. А. Аскеров Ф. И. Пепинов: Объединение операторов в логических схемах алгоритмов. Управление сетями связи и синтез управляющих устройств. Наука, Москв 1969, 34-41. | Zbl

[16] В. А. Горбатов: Синтез микропрограммых автоматов по временным диаграммам из функционирования. Цифровая вычислительная техника и программование, вып. 5. Советское радио, Москва 1969, 192-202. | Zbl

[17] Л. А. Кузнецов В. Л. Патрикеев: Минимизация матричных схем Янова. Кибернетика (Луганск. отд.), Тр. семинара, вып. 2, Киев 1969, 59-65. | Zbl

[18] В. Л. Патрикеев: Минимизация операторных схем Янова. Техническая кибернетика, вып. 6, Киев 1970, 72-81. | Zbl

[19] В. В. Сапожников, Вл. В. Сапожников: О преобразовании первичной таблицы переходов. Автоматика и телемеханика (1970), 5, 204-206. | Zbl

[20] В. Н. Гребенщиков: Комбинированный метод синтеза конечных автоматов. Изв. высш. учебн. заведений, Радиофизика 13 (1970), 11, 1736-1740. | Zbl

[21] J. Hartmanis R. E. Stearns: Some Dangers in State Reduction of Sequential Machines. Information and Control 5 (1962), 4, 252-260. | MR

[22] D. A. Huffmann: The Synthesis of Sequential Switching Circuits. J. Frank. Inst., 257 (1954), 3, 4, 161-190, 275-303. | MR

[23] G. H. Mealy: A Method for Synthesising Sequential Machines. B.S.T.J. 34 (1955), 5, 1045-1079. | MR

[24] D. D. Aufenkamp F. E. Hohn: Analysis of Sequential Machines. IRE Trans. Electr. Comput. 6 (1957), 6, 276-283. | MR

[25] D. D. Aufenkamp: Analysis of Sequential Machines. IRE Trans. Electr. Comput. 7 (1958), 2, 299-306.

[26] M. Phister: Logical Design of Digital Computers. John Willey and Sons, New York 1958. | MR | Zbl

[27] A. Gill: Introduction to the Theory of Finite State Machines. McGraw-Hill Book Comp., Inc., New York 1962. | MR | Zbl

[28] S. Ginsburg: An Introduction to Mathematical Machine Theory. Reading Mass. Addison-Wesley 1962. | MR | Zbl

[29] В. Г. Лазарев Е. И. Пийль: Уменышение числа состояний одного класса конечных автоматов. Доклады AH CCCP 143 (1962), 5, 1064-1066. | Zbl

[30] A. Železnikar: Ekvivalentnost i minimizacija apstraktnih automata. Automatika (1965), 2, 3, 133-141.

[31] P. E. Wood: Switching Theory. McGraw Hill, New York 1968. | Zbl

[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.

[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.

[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.

[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.

[36] A. Grasselli: Minimal Closed Partitions for Incompletely Specified Sequential Machines. Electron-Letters (1962), 2, 191-194.

[37] B. Г. Лазарев Е. И. Пийль: Синтез асинхронных конечных автоматов. Наука, Москва 1964. | Zbl

[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.

[39] В. И. Трошин: Алгебраический способ минимизации неполностью определенных последователъностных машин. Автоматика и телемеханика 26 (1965), 2, 2176-2181. | Zbl

[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. | MR | Zbl

[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.

[42] J. Gruel: Ein Beitrag zum Thema "Minimalautomaten". Wiss. Z. Techn. Univ. Dresden (1968), 5, 1109-1112. | MR | Zbl

[43] А. Грасселли Ф. Лучио: Метод совместной минимизации строк и столбцов таблицы переходов. Автоматика и телемеханика (1968), 8, 100-115. | Zbl

[44] A. Schmitt: Zur Theorie der nichtdeterministischen und unvollstandigen Automaten. Computing 4 (1969), 1, 56-74. | MR

[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.

[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

[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. | MR | Zbl

[48] U. Isphording: Ein Matrizenalgorithmus zur Minimizierzung der Schalteranzahl in Schalternetzwerken. Arch. elek. Übertrag. 24 (1970), 3, 132-138. | MR

[49] J. Kella: State Minimization of Incompletely Specified Sequential Machines. IEEE Trans. Comput. 19 (1970), 4, 342-348. | MR | Zbl

[50] T. Kameda P. Weiner: On the State Minimization of Nondeterministic Finite Automata. IEEE Trans. Comput. 19 (1970), 17, 617-627. | MR

[51] Z. Kohavi: Reduction of the Number of States in Incompletely Specified Sequential Machines. Electron. Letters (1965), 7, 712-715.

[52] Ю. В. Потосин E. А. Бутаков: Минимизация числа сотсояний последовательностного автомата. Труды Сибирского физико-технического института при Томском государственном университете им. В. В. Куйбышева, вып. 48 (1966), 165-180. | Zbl

[53] P. Hummitzsch: Zur Reduction von partiellen Automaten mit Eingangbeschrankungen. Messen-Steuern-Regeln (1968), 4, 124-129.

[54] Ю. В. Потосин: Экспериментальная оценка одного метода минимизации числа cостояний дискретного автомата. Сб. „Проблемы синтеза цифровых автоматов". Наука, Москва 1967, 101-107. | Zbl

[55] В. П. Диденко: О методах минимизации и построении мостиковых структур релейных устройств. Автомат. регулирование и управление. АН СССР, Москва 1962, 444-460. | Zbl

[56] Э. Дж. Мак-Класки: Многократные схемы с минимальным числом состояний для ограниченного класса неполностью определенных таблиц переходов. Теория конечных и вероятностных автоматов. Наука, Москва 1965, 362-371. | Zbl

[57] В. Г. Лазарев: Матричный метод минимизации схем микропрограмм. Известия АН СССР, Техническая кибернетика (1965), 2, 35-42. | Zbl

[58] А. А. Летичевский: О минимизации конечных автоматов. Кибернетика (1966), 1, 20-24. | Zbl

[59] О. В. Медведев: Минимизация числа состояний последовательностной машины при входных последовательностях, не содержащих двух одинаковых символов подряд. Автоматика и телемеханика (1966), 5, 117-124. | Zbl

[60] Э. А. Якубайтис А. Ю. Гобземис В. Г. Горбец Г. Ф. Фринцович: Минимизация объема памяти последовательностных логических схем. Автоматика и вычислительная техника, 12. Зинатне, Рига 1966. | Zbl

[61] М. С. Раul G. А. Waldbaum: A Note on State Minimization of Asynchronous Sequential Functions. IEEE Trans. Electr. Comput. 16 (1967), 1, 94-97.

[62] М. А. Спивак: К минимизации автоматов Мура. Кибернетика (1967), 1, 5-6. | Zbl

[63] А. Ю. Гобземис: Минимизация числа промежуточных переменных при синтезе последовательностных асинхронных логических схем. Теория дискретных автоматов. Зинатне, Рига 1967. | Zbl

[64] Г. Ф. Фринцович: Способ задания и распознавания эквивалентных устойчивых состояний последовательностных асинхронных логических схем. (ПАЛС). Теория дискретных автоматов. Зинатне, Рига 1967, 141-156. | Zbl

[65] Б. Г. Миркин: Минимизация последовательностных машин относительно регулярных, полных справа событий. Автоматика и телемеханика 11, (1967), 149-153. | MR | Zbl

[66] Н. J. Zander: Zur Zustandsreduction ungetakteter (asynchroner) Folgeschaltungen. Elektron. Informationsverarb. und Kybernetik, 4 (1968), 4-5, 257-277, 285-300.

[67] W. S. Brainerd: The Minimalization of Free Automata. Information and Control 13 (1968), 5, 484-491. | MR

[68] С. dе Renna e Sonza: A Theorem on the Reduction of Synthesized Stochastic Machines. IEEE Trans. Comput. 18 (1969), 5, 473-474.

[69] Е. А. Гурвиц: Синтез полисинхронных дискретных устройств. Связь, Москва 1969. | Zbl

[70] Д. Е. Черный: Алгебраические свойства частичных автоматов. Известия высш. учебн. заведений, Математика (1970), 2, 94-99. | Zbl

[71] Г. Ф. Фринцович: Минимизация числа состояний частично определенных асинхронных конечных автоматов. Автоматика и вычислительная техника (1970), 4, 1-7. | Zbl

[72] В. Т. Бардачевский В. М. Голованевский: Минимизация структурных схем конечных цифровых автоматов, построенных на феррит-транзисторных элементах. Отбор и передача информации, Респ. межвед. сб., вып. 25 (1970), 113-117. | Zbl

[73] W. Stucky H. Walter: Minimal Linear Realization of Autonomous Automata. Information and Control 16 (1970), 1, 66-84. | MR

[74] R. Hartenstein: Suchlistenstrukturen zur Darstellung gerichteter Graphen und deren Anwendung bei Synthese und Minimizierung spezieller endlicher Automaten. Elektr. Rechenanlagen (1970), 4, 208-216.

[75] А. Д. Закревский: Синтез последовательностных автоматов и его программирование. Применение вычислительной техники для автоматизации производства. Машгиз, Москва 1961, 525-534. | Zbl

[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.

[77] А. Д. Закревский: К синтезу последовательностных автоматов. Труды Сибирскогo физико-технического института, вып. 40 (1961), 89-94. | Zbl

[78] Е. А. Бутаков А. Д. Закревский: Минимизации числа осстояний релейной схемы на универсальной цифровой вычислительной машине ,,Урал". Проблемы передачи информации, вып. 11. Наука, Москва 1962.

[79] В. М. Глушков А. А. Летичевский А. А. Стогный: Алгоритмическая система для автоматизации синтеза цифровых автоматов. Синтез релейных структур, Москва 1965, 342-344. | Zbl

[80] Ю. В. Потосин: Алгоритмы минимизации числа состояний дискретного автомата. Логический язык для представления алгоритмов синтеза релейных устройств. Наука, Москва 1966, 301-325. | Zbl

[81] Ю. В. Потосин: К минимизации числа состояний дискретного автомата. Тезисы докладов Всесоюзного коллоквиума по автоматизации синтеза дискретных вычислительных устройств. Новосибирск 1966, 61-63. | Zbl

[82] W. Händler: Zur Theorie endlicher Automaten. Computer 1 (1966), 173-181.

[83] Ю. В. Потосин: Экспериментальная оценка одного метода минимизации числа состояний дискретного автомата. Проблемы синтеза цифровых автоматов. Наука, Москва 1967, 101-107. | Zbl

[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

[85] S. Ginsburg: On the Reduction of Superfluous States in a Sequential Machine. J.A.C.M. 6 (1959), 1, 252-282. | MR | Zbl

[86] E. J. McCluskey: Minimization of Boolean Functions. B.S.T.J. 35 (1956), 6, 1236-1249. | MR

[87] S. H. Unger: Flow Table Simplification Some Useful Aids. IEEE Trans. Electr. Comput. 14 (1965), 3, 472-475. | Zbl

[88] В. Ф. Дьяченко В. Г. Лазарев Г. Г. Саввин: Управление на сетях связи. Наука, Москва 1967. | Zbl

[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

[90] В. Г. Лазарев В. М. Ченцов: О минимизации числа внутренних состояний стохастического автомата. Синтез дискретных автоматов и управляющих устройств. Наука, Москва 1968, 150-159. | Zbl

[91] A. Graselli U. Montanari: On the Minimization of READY-ONLY Memories in Microprogrammed Digital Computers. IEEE Trans. Comput 19 (1970), 11, 1111-1114.

[92] A. S. Meisel: A Note on Internal State Minimization in Incompletely Specified Sequential Networks. IEEE Trans. Electr. Comput. 16 (1967), 4, 508-509.

[93] М. А. Гаврилов: Проблемы поиска минимальных решений при синтезе структуры релейных устройств. Труды III Всесоюзного совещания по автоматическому управлению (техн. кибернетике). Самонастраивающиеся системы. Распознавание образцов. Релейные устройства и конечные автоматы. Наука, Москва 1967, 289-303. | Zbl

[94] Техническая кибернетика, Проблемы управления и информации. Вопросы советской науки. Наука, Москва 1966. | Zbl

[95] J. Hartmanis: Loop-free Structure of Sequential Machines. Information and Control 5 (1962), 2, 25-43. | MR | Zbl

[96] E. H. Faar: Lattice Properties of Sequential Machines. J.A.C.M. (1963), 3, 365-385. | MR

[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.

[98] Е. Н. Вавилов Д. Б. Шишков: Об одном методе экономичного кодирования автоматов. Известия АН СССР, Техническая кибернетика (1967), 2, 104-113. | Zbl

[99] М. А. Айзерман Л. А. Гусев Л. И. Розоноэр И. М. Смирнова А. А. Таль: Логика, автоматы, алгоритмы. Физматгиз, Москва 1963. | Zbl

[100] Д. Б. Шишков: Декомпозиция автоматов в виде иерархических и каскадных структур. Доклады Болгарской академии наук 1 (1968), 21, 27-29. | Zbl