УДК 510.55 |
С. А. Бадаев, С. С. Гончаров, А. Cорби |
Типы изоморфизмов полурешёток Роджерса семейств из различных уровней арифметической иерархии, 637—654. |
Исследуется несовпадение типов изоморфизма полурешёток Роджерса вычислимых нумераций семейств множеств из различных уровней арифметической иерархии. |
Ключевые слова: арифметическая иерархия, вычислимая нумерация, полурешётка Роджерса. |
Адреса авторов:
Бадаев Серикжан Агыбаевич, Казахский нац. ун-т, ул. Масанчи, 39/47, г. Алматы, 480012, Казахстан. e-mail: badaev@kazsu.kz
|
УДК 512.579 |
А. А. Булатов |
Комбинаторная задача CSP позволяет выразить в единых терминах широкий спектр задач из различных областей математики, информатики и искусственного интеллекта. Общая задача CSP является NP-полной, однако многие ограниченные версии этой задачи могут быть решены за полиномиальное время. Известно, что вычислительная сложность ограниченных задач CSP зависит лишь от множества полиморфизмов отношений, которые разрешено использовать в задаче. В случае, когда множество разрешённых отношений инвариантно относительно некоторой мальцевской операции, показывается, что соответствующая задача CSP может быть решена за полиномиальное время. |
Ключевые слова: вычислительная сложность задачи, задача CSP, мальцевская операция. |
Адрес автора: Булатов Андрей Арнольдович, каф. алгебры и дискр. матем., Уральский гос. ун-т, ул. Ленина, 51, г. Екатеринбург, 620083, Россия. Тел.: (343) 350-75-79, e-mail: andrei.bulatov@usu.ru |
УДК 512.58+510.67 |
Е. И. Бунина, А. В. Михалёв |
Элементарные свойства категории полигонов над моноидом, 687—709. |
Изучается взаимосвязь между элементарной эквивалентностью категорий полигонов над моноидами и эквивалентностью в логике второго порядка данных моноидов. |
Ключевые слова: элементарная эквивалентность, теория второго порядка, категория полигонов над моноидами. |
Адреса авторов:
Бунина Елена Игоревна, каф. высш. алгебры, мех.-матем. ф-т, ГЗ МГУ им. М. В. Ломоносова,
Ленинские горы, Москва, 119992, ГСП-2, Россия. Тел.: (495) 939-16-11, e-mail: helenbunina@yandex.ru
|
УДК 512.54+512.57 |
В. Го, А. Н. Скиба, К. П. Шам |
Исследуются решётки подгрупповых и подсистемных функторов. В частности, доказывается, что в случае, когда ${\cal X}$ — формация конечных групп, а ширина решётки $F_{0}({\cal X})$ не превосходит $|\pi ({\cal X})|$, формация ${\cal X}$ метанильпотентна и $|\pi ({\cal X})| \leqslant 3$. |
Ключевые слова: подсистемный функтор, подгрупповой функтор, решётка подсистемных функторов, решётка подгрупповых функторов. |
Адреса авторов:
Го Вэньбинь, ф-т матем., Худжоуский нормаль. ун-т, г. Худжоу, 221009, КНР. е-mail: wbguo@pub.xz.jsinfo.net
|
УДК 510.64 |
О. В. Зеевальд |
Нечёткие логики с модальностями, 731—757. |
Исследуются базисная нечёткая логика $BL$, а также пропозициональные нечёткие логики с модальностями $\Box, \diamond$ и тотальным отношением достижимости. Приводятся формулировки и доказательства теорем о замене для $BL$. Вводится базисное исчисление модальной нечёткой логики. Для этого исчисления и его расширений доказываются теоремы о замене и о дедукции. |
Ключевые слова: базисная нечёткая логика, $BL$-алгебра, модальность, $L$-структура Крипке, исчисление, схематическое расширение, теорема о замене, теорема о дедукции. |
Адрес автора: Зеевальд Ольга Владимировна, Ин-т матем. СО РАН, пр. Ак. Коптюга, 4, г. Новосибирск, 630090, Россия. e-mail: neona@gorodok.net |
УДК 510.5 |
З. Г. Хисамиев |
Любое подсемейство данного не более чем счётного непустого семейства можно сделать множеством всех особых элементов подходящей нумерации. |
Ключевые слова: нумерация, полная нумерация, пополнение, особый элемент, $\Sigma_{n}^0$-вычислимая нумерация. |
Адрес автора: Хисамиев Зариф Гарифуллинович, Орбита-1, д. 25, кв. 58, г. Алма-Ата, Казахстан. Тел.: 290224. e-mail: KhisamievZ@kazsu.kz |