|
Алгебра и логика, 1995, том 34, номер 6, страницы 667–680
(Mi al2332)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Рекурсивно несовместные алгоритмические проблемы на $1$-конструктивизируемых дистрибутивных решетках с относительными дополнениями
С. Т. Федоряев Институт математики Сибирского отделения Российской академии наук, г. Новосибирск
Аннотация:
Для произвольной $1$-конструктивизируемой дистрибутивной решетки $\mathfrak{A}$ с относительными дополнениями и бесконечным множеством атомов строится вычислимое семейство $\Omega$ алгоритмических $\sigma_2^r$-проблем на $\mathfrak{A}$, каждая из которых разрешима при подходящей конструктивизаций решетки $\mathfrak{A}$, но при любой конструктивизации произвольные две алгоритмические проблемы из $\Omega$ не могут быть одновременно разрешимы. Тем самым для $1$-конструктивизируемых дистрибутивных решеток с относительными дополнениями получается решение проблем спектра и соотношений алгоритмических размерностей и находятся критерии существования наименьшего элемента в структуре алгебраической сводимости и алгебраические условия решения задачи эффективного выбора конструктивизаций по спецификациям проблем.
Поступило: 29.06.1994
Образец цитирования:
С. Т. Федоряев, “Рекурсивно несовместные алгоритмические проблемы на $1$-конструктивизируемых дистрибутивных решетках с относительными дополнениями”, Алгебра и логика, 34:6 (1995), 667–680
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al2332 https://www.mathnet.ru/rus/al/v34/i6/p667
|
|