О ЗАДАЧЕ ВЫРАЗИМОСТИ АВТОМАТОВ ОТНОСИТЕЛЬНО СУПЕРПОЗИЦИИ ДЛЯ СИСТЕМ С ФИКСИРОВАННОЙ ДОБАВКОЙ
Ключевые слова:
конечный автомат, выразимости, алгоритм, группаАннотация
Рассматривается задача выразимости конечного группового автомата Медведева cуперпозициями систем вида , где Ф состоит из всех булевых функций и «задержки», - произвольная конечная cистема автоматов. Ранее автор показал, что для группового автомата Медведева группа которого является разрешимой, существует алгоритм проверки . В настоящей работе решается задача выразимости через системы произвольных групповых автоматов Медведева.Библиографические ссылки
Кудрявцев В. Б., Алешин С. В., Подколзин А. С. Введение в теорию автоматов. - М. : Наука. Гл. ред. физ.-мат. лит., 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.
