М. В. Зубков, И. Ш. Калимуллин, А. Г. Мельников, А. Н. Фролов, “Пунктуальные копии алгебраических структур”, Сиб. матем. журн., 2019, том 60, номер 6,страницы 1271

Эта публикация цитируется в 4 статьях

Пунктуальные копии алгебраических структур

М. В. Зубков^a, И. Ш. Калимуллин^a, А. Г. Мельников^b, А. Н. Фролов^a

^a Казанский (Приволжский) федеральный университет, ул. Кремлевская, 35, Казань 420008
^b Massey University East Precinct, Dairy Flat Highway (SH17), 0632, New Zealand

Аннотация: Оценивается сложность построения пунктуальной «онлайн» копии алгебраической структуры. Установлены общая верхняя оценка, а также оптимальные оценки для классов булевых алгебр, абелевых $p$-групп и линейных порядков. Кроме того, развитые здесь методы применяются для решения открытой проблемы Монталбана (2013) о копируемых линейных порядках.

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

УДК: 510.5

Статья поступила: 14.12.2018
Окончательный вариант: 26.03.2019
Принята к печати: 15.05.2019

DOI: 10.33048/smzh.2019.60.607