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

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

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



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






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


Сиб. матем. журн., 2019, том 60, номер 3, страницы 489–505 (Mi smj3090)  

О разрешимости списочных структур

С. А. Александроваa, Н. А. Баженовba

a Новосибирский государственный университет, ул. Пирогова, 1, Новосибирск 630090
b Институт математики им. С. Л. Соболева СО РАН, пр. Академика Коптюга, 4, Новосибирск 630090

Аннотация: Изучается теоретико-вычислимая сложность различных структур, основанных на списочном типе данных. Списочная надстройка над структурой $S$ содержит два сорта элементов: атомы из $S$ и конечные линейные списки атомов. Сигнатура списочной надстройки состоит из сигнатуры $S$, пустого списка $nil$ и бинарной операции присоединения атома к списку. Обогащенная списочная надстройка над $S$ получается добавлением к сигнатуре дополнительных функций и отношений: взятия последнего элемента списка, получения остатка списка после удаления последнего элемента, отношения принадлежности атома к списку и отношения «быть начальным сегментом списка».
Доказано, что элементарная теория обогащенной списочной надстройки над $(\omega, +)$, т. е. моноида натуральных чисел относительно сложения, вычислимо изоморфна арифметике первого порядка. В частности, это означает, что преобразование структуры $S$ в обогащенную списочную надстройку над $S$ не всегда сохраняет разрешимость элементарных теорий. Также показано, что списочная надстройка над $S$ может быть представлена с помощью конечного автомата в том и только том случае, когда $S$ конечна.

Ключевые слова: линейный список, списочная надстройка, разрешимая структура, автоматная структура, древесно-автоматная структура.

Финансовая поддержка Номер гранта
Российский фонд фундаментальных исследований 18-41-543015_р_мол_а
Российский научный фонд 18-11-00028
Работа С. А. Александровой выполнена при финансовой поддержке Российского фонда фундаментальных исследований (код проекта № 18–41–543015 р_мол_а). Исследования Н. А. Баженова выполнены за счет гранта Российского научного фонда (проект № 18–11–00028).


DOI: https://doi.org/10.33048/smzh.2019.60.302

Полный текст: PDF файл (366 kB)
Первая страница: PDF файл
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 510.674+519.713
Статья поступила: 10.07.2018
Окончательный вариант: 10.07.2018
Принята к печати: 19.12.2018

Образец цитирования: С. А. Александрова, Н. А. Баженов, “О разрешимости списочных структур”, Сиб. матем. журн., 60:3 (2019), 489–505

Цитирование в формате AMSBIB
\RBibitem{AleBaz19}
\by С.~А.~Александрова, Н.~А.~Баженов
\paper О~разрешимости списочных структур
\jour Сиб. матем. журн.
\yr 2019
\vol 60
\issue 3
\pages 489--505
\mathnet{http://mi.mathnet.ru/smj3090}
\crossref{https://doi.org/10.33048/smzh.2019.60.302}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/smj3090
  • http://mi.mathnet.ru/rus/smj/v60/i3/p489

    ОТПРАВИТЬ: 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
  • Сибирский математический журнал Siberian Mathematical Journal
    Просмотров:
    Эта страница:82
    Литература:16
    Первая стр.:4
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019