О ЗАДАЧЕ ВЫРАЗИМОСТИ АВТОМАТОВ ОТНОСИТЕЛЬНО СУПЕРПОЗИЦИИ ДЛЯ СИСТЕМ С ФИКСИРОВАННОЙ ДОБАВКОЙ

Авторы

  • А. А. Летуновский ООО «ЭлЭсАй Интернешнел Ресерч», Москва

Ключевые слова:

конечный автомат, выразимости, алгоритм, группа

Аннотация

Рассматривается задача выразимости конечного группового автомата Медведева 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.

Загрузки

Опубликован

15.03.2012

Как цитировать

Летуновский, А. А. (2012). О ЗАДАЧЕ ВЫРАЗИМОСТИ АВТОМАТОВ ОТНОСИТЕЛЬНО СУПЕРПОЗИЦИИ ДЛЯ СИСТЕМ С ФИКСИРОВАННОЙ ДОБАВКОЙ. Интеллектуальные системы в производстве, 7(1), 36–50. извлечено от https://izdat.istu.ru/index.php/ISM/article/view/1399

Выпуск

Раздел

Статьи