|
Discrete mathematics in relation to computer science
Степени перечислимости ограниченных множеств
Б. Я. Солон Ивановский государственный университет, ул. Ермака, д.39, г. Иваново, 153025 Россия
Аннотация:
Термин «тотальная степень перечислимости» связан с тем, что $e$-степень тотальна тогда и только тогда, когда она содержит график некоторой тотальной функции. В ряде работ автора и группы математиков из University of Wisconsin-Madison рассматривались так называемые «граф-кототальные степени перечислимости», т.е. $e$-степени, содержащие дополнение графика некоторой тотальной функции $f(x)$. В данной статье сделан следующий шаг – рассмотрены степени перечислимости множеств, ограниченных сверху или снизу графиком тотальной функции. Более точно, множество $A$ ограничено сверху, если $A=\{\langle x,y\rangle:y < f(x)\}$ для некоторой тотальной функции $f(x)$ и множество $A$ ограничено снизу, если $A=\{\langle x,y\rangle:y > f(x)\}$ для некоторой тотальной функции $f(x)$.
В статье приводится ряд результатов, показывающих существование нетотальных степеней перечислимости, содержащих ограниченные множества, причем построенные $e$-степени являются квазиминимальными. Важным является результат, утверждающий, что ограниченные множества обладают свойством Фридберга, связанным с инверсией скачка.
Ключевые слова:
степени перечислимости, квазиминимальные степени перечислимости, ограниченные множества.
Поступила в редакцию: 27.04.2022 Исправленный вариант: 23.05.2022 Принята в печать: 25.05.2022
Образец цитирования:
Б. Я. Солон, “Степени перечислимости ограниченных множеств”, Модел. и анализ информ. систем, 29:2 (2022), 104–114
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mais770 https://www.mathnet.ru/rus/mais/v29/i2/p104
|
Статистика просмотров: |
Страница аннотации: | 44 | PDF полного текста: | 21 | Список литературы: | 17 |
|