С. С. Гончаров, Н. А. Баженов, М. И. Марчук, “Индексное множество автоустойчивых относительно сильных конструктивизаций булевых алгебр”, Сиб. матем. журн., 2015, том 56, номер 3,страницы 498

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

Индексное множество автоустойчивых относительно сильных конструктивизаций булевых алгебр

С. С. Гончаров^ab, Н. А. Баженов^ba, М. И. Марчук^a

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

Аннотация: Получены точные оценки алгоритмической сложности для классов сильно конструктивизируемых вычислимых моделей, являющихся автоустойчивыми относительно сильных конструктивизаций и принадлежащих следующим естественным классам: булевым алгебрам, дистрибутивным решеткам, кольцам, коммутативным полугруппам, частичным порядкам.

Ключевые слова: вычислимая модель, сильно конструктивизируемая модель, автоустойчивость, автоустойчивость относительно сильных конструктивизаций, булева алгебра, дистрибутивная решетка, кольцо, коммутативная полугруппа, частичный порядок, гиперарифметическая иерархия, индексное множество.

УДК: 510.5+512.563

Статья поступила: 18.03.2015

DOI: 10.17377/smzh.2015.56.303