УДК 510.57

Э. Ф. Комбарро

Группы автоморфизмов вычислимо перечислимых предикатов, 515—530.

Изучаются группы автоморфизмов двух важнейших предикатов в теории вычислимости: предиката $x \in W_y$ и графика универсальной частичной вычислимой функции. Показывается, что все автоморфизмы этих предикатов вычислимы. Изучается действие этих групп на некоторых индексных  множествах и устанавливаются некоторые результаты о структуре этих групп. Изучаются гомоморфизмы этих двух предикатов. В этом случае ситуация меняется: все гомоморфизмы универсальной функции вычислимы,  но в каждой тьюринговой степени существуют гомоморфизмы предиката $x \in W_y$.

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

Адрес автора: Elias Fernandez-Combarro Alvarez, Departamento de Informatica, Universidad de Oviedo, Campus de Viesques, 33271 Gijon, Espana. e-mail: elias@orion.ciencias.uniovi.es

УДК 510.5+510.6

Ч. Ф. Д. Мак-Кой

О $\Delta_{3}^{0}$-категоричности для линейных порядков и булевых алгебр, 531—552.

Исследуется $\Delta_{3}^{0}$-категоричность для линейных порядков и булевых алгебр. Доказывается, что существует несчетное число относительно $\Delta_{3}^{0}$-категоричных линейных порядков. Показывается, что задача классификации (неотносительно) $\Delta_{3} ^{0}$-категоричных линейных порядков может оказаться очень сложной. Полной противоложностью этим результатам для линейных порядков является полное описание относительно $\Delta_{3}^{0}$-категоричных булевых алгебр, которое также приводится.

Ключевые слова: линейный порядок, булева алгебра, $\Delta_{3}^{0}$-категоричность.

Адрес автора: McCoy Ch. F. D., University of Wisconsin, Madison, WI 53706, USA. e-mail: mccoy@math.wisc.edu

УДК 512.544.4

Е. Л. Первова

Конгруэнц-свойство АТ-групп, 553—567.

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

Ключевые слова: АТ-группа, периодическая группа, конгруэнц-свойство, проблема сопряженности, свойство отделимости относительно сопряженности.

Адрес автора: Первова Екатерина Львовна, Россия, 454017, г. Челябинск, ул. Дегтярева, д. 55, кв. 64. Тел.: 24-74-12. e-mail: pervova@cgu.chel.su

УДК 510.5

В. Г. Пузаренко

О разрешимых вычислимых $\mathbb{A}$-нумерациях, 568—584.

Рассматриваются нумерации на допустимых множествах, которые Ю. Л. Ершов ввел  в книге "Определимость и вычислимость".  Для моделей двух специальных классов решается проблема существования однозначных вычислимых нумераций семейств всех вычислимых множеств и вычислимых функций. В первом случае при доказательстве конечными объектами служат синтаксические конструкции, а во втором — конечные подмножества наследственно конечной надстройки.

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

Адрес автора: Пузаренко Вадим Григорьевич, Россия, 630090, г. Новосибирск,  пр. ак. Коптюга, 4, Институт математики СО РАН. e-mail: vagrig@math.nsc.ru

УДК 510.643+519.72

В. В. Рыбаков

Информационные фреймы Барвайса и модальные логики, 585—609.

Исследуются введенные Дж. Барвайсом информационные фреймы и решается поставленная им задача аксиоматизации модальных логик, порожденных информационными фреймами. Построены аксиоматические системы для модальных логик (i) всех полных информационных фреймов,  (ii) всех правильных и полных информационных фреймов,  (iii) всех наследственных и полных информационных фреймов, (iv) всех полных, правильных и наследственных информационных фреймов и (v) всех совместных и полных информационных фреймов. Вводится понятие слабой модальной логики и показывается, что слабая модальная логика, порожденная всеми информационными фреймами, совпадает с $K$, а порожденная всеми наследственными информационными фреймами — с $K4$. В развитие общей теории доказывается, что всякая полная по Крипке модальная логика является модальной логикой некоторого класса информационных фреймов и что модальная логика, порожденная произвольным классом полных, разреженных и вполне классифицированных информационных фреймов, полна по Крипке.

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

Адрес автора: Рыбаков Владимир Владимирович, Department of Computing and Mathematics, Manchester Metropolitan University, All Saints, Manchester M15 6BH, United Kingdom. e-mail: V.Rybakov@mmu.ac.uk

УДК 510.532+519.713.2

В. Л. Селиванов

О разрешимости классов иерархий регулярных апериодических языков, 610—631.

Предлагается новый, логический подход к проблеме разрешимости для иерархий Страубинга и Бжозовского, основанный на теоремах об устойчивости из теории моделей, на одной теореме Хигмана и на теореме Рабина о дереве. Таким путем удается получить чисто логические короткие доказательства некоторых известных фактов о разрешимости, что может представлять определенный методологический интерес. Данный подход применим также в некоторых других подобных ситуациях, например, для иерархий формул по модулю теории линейных порядков с конечным числом унарных предикатов.

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

Адрес автора: Селиванов Виктор Львович, Россия, 630126, г. Новосибирск, ул. Вилюйская, 28, Педагогический университет, математический факультет. e-mail: vseliv@nspu.ru