Problem of automata expressability realtive to superposition for systems with fixed additive
Keywords:
finite automaton, expressibility, algorithm, groupAbstract
The paper cosiders expressibility problem of finite group Medvedev automatonrelative to superposition of systems , where Ф consists of all Boolean functions and delay, is the arbitrary finite system of automata. The author showed previously, that there is the testing algorithm for group Medvedev automaton with the solvable group. The present paper is devoted to solution of expressibility problem relative to system of arbitrary group automata.References
Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. - М. : Наука. Гл. ред. физ.-мат. лит., 1985. - 320 с.
Бабин Д. Н. О полноте двухместных автоматных функций относительно суперпозиции // Дискрет. матетматика. - 1989. - Т. 1, вып. 4. - С. 423-431. - URL: http://rrc.dgu.ru/res/mat/intsys.msu.ru/staff/babin/gilbert.pdf (дата <http://depositfiles.com/files/a8dtsfceh (дата> обращения: 17.05.2012).
Кратко М. И. Алгоритмическая неразрешимость проблемы распознавания полноты для конечных автоматов // Докл. АН СССР. - 1964. - Т. 155, № 1. - С. 35-37.
Летуновский А. А. О выразимости константных автоматов // Интеллектуал. системы. - 2005. - Т. 9, вып. 1-4. - С. 457-469. - URL: http://intsys.msu.ru/magazine/archive/v9%281-4%29/letunovskiy-457-468.pdf (дата <http://depositfiles.com/files/a8dtsfceh (дата> обращения: 17.05.2012).
Бабин Д. Н. О классификации автоматных базисов Поста по разрешимости свойств полноты и А-полноты // Докл. Акад. наук. - 1999. - Т. 367, № 4. - С. 439-441.
Мальцев А. И. Итеративные алгебры и многообразие Поста // Алгебра и логика. - 1966. - Т. 5, № 2. - С. 5-24.
Летуновский А. А. О выразимости суперпозициями автоматов c разрешимыми группами (в печати).
Летуновский А. А. О выразимости константных автоматов суперпозициями // Интеллектуал. системы. - 2009. - Т. 13, вып. 1-4. - С. 397-406. - URL: http://intsys.msu.ru/magazine/archive/v13%281-4%29/letunovskiy-397-406.pdf (дата <http://depositfiles.com/files/a8dtsfceh (дата> обращения: 17.05.2012).
Каргаполов М. И., Мерзляков Ю. И. Основы теории групп. - 3-е изд., перераб. и доп. - М. : Наука, 1982. - 288 с. - URL: <http://depositfiles.com/files/a8dtsfceh (дата> обращения: 17.05.2012).
Алгебраическая теория автоматов, языков и полугрупп / под ред. М. А. Арбиба ; пер. с англ. Н. И. Осетинского. - М. : Статистика, 1975. - 336 с. - URL: http://bookfi.org/dl/437779/03ddc1 (дата <http://depositfiles.com/files/a8dtsfceh (дата> обращения: 17.05.2012).
Алешин С. В. Об одном следствии теоремы Крона - Роудза // Дискрет. математика. - 1999. - Т. 11, вып. 4. - С. 101-109.
