|
Эта публикация цитируется в 7 научных статьях (всего в 7 статьях)
Об алгоритмической неразрешимости распознавания $A$-полноты для ограниченно-детерминированных
функций
В. А. Буевич
Вычислительный центр АН СССР
Аннотация:
Рассматривается функциональная система $P$, элементами которой являются отображения, осуществляемые так называемыми конечными автоматами, ограниченно-детерминированные функции (о.-д. функции), а операциями — операции суперпозиции. Система $\mathfrak{M}$ о.-д. функций называется $A$-полной, если для любой о.-д. функции и для всякого натурального $\tau>0$ из о.-д. функции системы $\mathfrak{M}$ с помощью операций суперпозиции можно получить о.-д. функцию, совпадающую с заданной на словах длины $\tau$. Возникает вопрос: существует ли алгоритм для распознавания $A$-полноты произвольной конечной системы о.-д. функции? Показывается, что такого алгоритма не существует. Библ. 4 назв.
 Полный текст:
PDF файл (1445 kB)
Англоязычная версия:
Mathematical Notes, 1972, 11:6, 417–421
Реферативные базы данных:
 
Тип публикации:
Статья
УДК:
519.9
Поступило: 17.03.1971
Образец цитирования:
В. А. Буевич, “Об алгоритмической неразрешимости распознавания $A$-полноты для ограниченно-детерминированных
функций”, Матем. заметки, 11:6 (1972), 687–697; Math. Notes, 11:6 (1972), 417–421
Цитирование в формате AMSBIB
\RBibitem{Bue72}
\by В.~А.~Буевич
\paper Об алгоритмической неразрешимости распознавания $A$-полноты для ограниченно-детерминированных
функций
\jour Матем. заметки
\yr 1972
\vol 11
\issue 6
\pages 687--697
\mathnet{http://mi.mathnet.ru/mz9837}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=313028}
\zmath{https://zbmath.org/?q=an:0265.02032|0251.02047}
\transl
\jour Math. Notes
\yr 1972
\vol 11
\issue 6
\pages 417--421
\crossref{https://doi.org/10.1007/BF01093729}
Образцы ссылок на эту страницу:
http://mi.mathnet.ru/mz9837 http://mi.mathnet.ru/rus/mz/v11/i6/p687
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
Эта публикация цитируется в следующих статьяx:
-
В. Б. Кудрявцев, “Алгебры автоматов”, Фундамент. и прикл. матем., 15:4 (2009), 37–66
 ; V. B. Kudryavtsev, “Automata algebras”, J. Math. Sci., 169:4 (2010), 435–456 -
М. А. Подколзина, “О полноте и $A$-полноте $S$-множеств детерминированных функций, содержащих все одноместные детерминированные $S$-функции”, Дискрет. матем., 21:2 (2009), 75–87
 ; M. A. Podkolzina, “On completeness and $A$-completeness of $S$-sets of determinate functions containing all one-place determinate $S$-functions”, Discrete Math. Appl., 19:3 (2009), 263–276 -
Д. Н. Жук, “О классификации автоматных базисов Поста по разрешимости свойств $A$-полноты для дефинитных автоматов”, Дискрет. матем., 22:2 (2010), 80–95 ; D. N. Zhuk, “On the classification of Post automaton bases by the decidability of the $A$-completeness property for definite automata”, Discrete Math. Appl., 20:3 (2010), 337–355
-
Жук Д.Н., “Критерий разрешимости проблемы a-полноты для дефинитных автоматов”, Доклады Академии наук, 439:1 (2011), 18–20
-
В. А. Буевич, М. А. Подколзина, “Об алгоритмической разрешимости задачи об $A$-полноте для систем ограниченно-детерминированных функций, содержащих все одноместные $S$-о.-д. функции”, Дискрет. матем., 24:4 (2012), 56–69 ; V. A. Buevich, M. A. Podkolzina, “On algorithmic solvability of the $A$-completeness problem for systems of boundedly determinate functions containing all one-place boundedly determinate $S$-functions”, Discrete Math. Appl., 22:5-6 (2012), 555–569
-
И. Е. Иванов, “Об автоматных функцияx с магазинной памятью”, Интеллектуальные системы. Теория и приложения, 22:1 (2018), 39–110
-
А. А. Часовских, “Проблема полноты в классах линейных автоматов”, Интеллектуальные системы. Теория и приложения, 22:2 (2018), 151–153
|
| Просмотров: |
| Эта страница: | 117 | | Полный текст: | 51 | | Первая стр.: | 1 |
|
Пользовательское соглашение