Problem of automata expressability realtive to superposition for systems with fixed additive

Letunovskiy A.A.

Abstract


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.

Keywords


finite automaton; expressibility; algorithm; group

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


Article Metrics

Metrics Loading ...

Metrics powered by PLOS ALM

Refbacks

  • There are currently no refbacks.


Copyright (c) 2012 Алексей Александрович Летуновский

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

ISSN 1813-7911