RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Скоро в журнале
Архив
Импакт-фактор
Подписка
Правила для авторов
Лицензионный договор
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Матем. заметки:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Матем. заметки, 1972, том 11, выпуск 6, страницы 687–697 (Mi mz9837)  

Эта публикация цитируется в 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

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. В. Б. Кудрявцев, “Алгебры автоматов”, Фундамент. и прикл. матем., 15:4 (2009), 37–66  mathnet  mathscinet; V. B. Kudryavtsev, “Automata algebras”, J. Math. Sci., 169:4 (2010), 435–456  crossref
    2. М. А. Подколзина, “О полноте и $A$-полноте $S$-множеств детерминированных функций, содержащих все одноместные детерминированные $S$-функции”, Дискрет. матем., 21:2 (2009), 75–87  mathnet  crossref  mathscinet  elib; 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  crossref
    3. Д. Н. Жук, “О классификации автоматных базисов Поста по разрешимости свойств $A$-полноты для дефинитных автоматов”, Дискрет. матем., 22:2 (2010), 80–95  mathnet  crossref  mathscinet  zmath  elib; 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  crossref  elib
    4. Жук Д.Н., “Критерий разрешимости проблемы a-полноты для дефинитных автоматов”, Доклады Академии наук, 439:1 (2011), 18–20  elib
    5. В. А. Буевич, М. А. Подколзина, “Об алгоритмической разрешимости задачи об $A$-полноте для систем ограниченно-детерминированных функций, содержащих все одноместные $S$-о.-д. функции”, Дискрет. матем., 24:4 (2012), 56–69  mathnet  crossref  mathscinet  elib; 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  crossref
    6. И. Е. Иванов, “Об автоматных функцияx с магазинной памятью”, Интеллектуальные системы. Теория и приложения, 22:1 (2018), 39–110  mathnet
    7. А. А. Часовских, “Проблема полноты в классах линейных автоматов”, Интеллектуальные системы. Теория и приложения, 22:2 (2018), 151–153  mathnet
  • Математические заметки Mathematical Notes
    Просмотров:
    Эта страница:117
    Полный текст:51
    Первая стр.:1
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020