INTERMEDIATE ALGEBRA OF TRANSITIONS IN MICROPROGRAM FINAL-STATE MACHINE
DOI:
https://doi.org/10.15588/1607-3274-2016-1-8Keywords:
microprogram final-state machine, partial function of transitions, intermediate algebra of transitions, final-state machine with counter.Abstract
The problem of formalization of representation of final-state machine, where the part of automaton transition is realized in noncanonicalway, is solved. A new approach for organization of the function of transitions of the final-state machine is proposed. According to
it the function of transitions is represented as a family of partial functions, each of which is defined only on the part of the domain of the
function of transitions, and corresponds to a subset of the automaton transitions. According to the proposed approach the traditional representation of the final-state machine as a polybasic algebra is changed. First, the mutual independence of the function of transitions and function of outputs that form the signature of algebra, allows us to consider them separately from each other. This way leads to presentation of the final-state machine as two algebras: the algebra of transitions whose signature contains only the function of transitions and algebra of outputs whose signature contains only the function of outputs. Second, the representation of the function of transitions in the form of a set of partial functions leads to the replacement of the algebra of transitions by the set of subalgebras of transitions, a signature of each of which is formed by partial function of transitions.
The example of the final-state machine with a counter shows that the law of transformation of codes of states within a certain subset of
transitions can be set by an algebraic function (operation of transitions) using scalar interpretation of codes of states of the structural finalstate
machine. The representation of scalar interpretation of codes of states and the operation of transitions as so-called intermediate algebra
of transitions isomorphic to both according subalgebras of transitions of the abstract and equivalent structural final-state machines is proposed.
References
Баранов С. И. Синтез микропрограммных автоматов / С. И. Баранов. – Л. : Энергия, 1979. – 232 с. 2. Алгебраическая теория автоматов, языков и полугрупп / под ред. М. Арбиба ; пер. с англ. – М. : Статистика, 1975. – 335 с. 3. Плоткин Б. И. Элементы алгебраической теории автоматов: учеб. пособие для вузов / Б. И. Плоткин, Л. Я. Гринглаз, А. А. Гварамия. – М. : Высшая школа, 1994. – 191 с. 4. Мальцев А. И. Алгебраические системы / А. И. Мальцев. – М. : Наука, 1970. – 392 с. 5. Плоткин Б. И. Универсальная алгебра, алгебраическая логика и базы данных / Б. И. Плоткин. – М. : Наука, гл. ред. физ.-мат. лит., 1991. – 448 с. 6. Судоплатов С. В. Элементы дискретной математики : учебник / С. В. Судоплатов, Е. В. Овчинникова. – М. : ИНФРА-М, Новосибирск : Изд-во НГТУ, 2002. – 280 с. 7. Богомолов А. М. Алгебраические основы теории дискретных систем / А. М. Богомолов, В. Н. Салий. – М. : Наука-Физматлит, 1997. – 368 с. 8. Новиков Ф. А. Дискретная математика для программистов / Ф. А. Новиков. – СПб. : Питер, 2000. – 304 с. 9. Кудрявцев В. Б. Введение в теорию автоматов / В. Б. Кудрявцев, С. В. Алешин, А. С. Подколзин. – М. : Наука, 1985. – 320 с. 10. Глушков В. М. Синтез цифровых автоматов / В. М. Глушков. – М. : Физматгиз, 1962. – 476 с. 11. Глушков В. М. Абстрактная теория автоматов / В. М. Глушков // Успехи математических наук. – 1961. – Т. XVI, Вып. 5. – С. 3–62. 12. Трахтенброт Б.А. Конечные автоматы (поведение и синтез) / Б. А. Трахтенброт, Я.М. Бардзинь. – М. : Наука, 1970. – 400 с. 13. Шиханович Ю. А. Введение в современную математику (начальные понятия) / Ю. А. Шиханович. – М. : Наука, 1965. – 376 с.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2016 R. M. Babakov
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
