Об индексном множестве пунктуально категоричных конечнопорожденных структур
Аннотация
Статья посвящена оценке индексного множества конечнопорожденных структур, имеющих с точностью до пунктуального изоморфизма единственное пунктуальное представление. Показано, что это индексное множество является Π03 -полным.
Об авторе
А. А. Курмачева
Казанский (Приволжский) федеральный университет
Россия
Россия
Кафедра алгебры и математической логики
ул. Кремлевская, д. 18, г. Казань, 420008
Список литературы
1. I. Sh. Kalimullin, A. G. Melnikov, K. M. Ng, Algebraic structures computable without delay, Theoret. Comput. Sci. 674, 73–98 (2017). DOI: https://doi.org/10.1016/j.tcs.2017.01.029
2. П. Е. Алаев, Полиномиально вычислимые структуры с конечным числом порождающих, Алгебра и логика 59 (3), 385–394 (2020). DOI: https://doi.org/10.33048/alglog.2020.59.307
3. R. I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Perspectives in math. logic. Springer-Verlag, Berlin, Heidelberg, New York, etc., 1987. URL: https://link.springer.com/book/9783540666813
4. N. A. Bazhenov, R. G. Downey, A. G. Melnikov, I. Sh. Kalimullin, Foundations of online structure theory, Bull. Symb. Log. 25 (2), 141–181 (2019). DOI: https://doi.org/10.1017/bsl.2019.20
5. И. Ш. Калимуллин, О построении пунктуально категоричных полугрупп, Алгебра и логика 59 (5), 600–605 (2020). DOI: https://doi.org/10.33048/alglog.2020.59.507
Рецензия
Для цитирования:
Курмачева А.А. Об индексном множестве пунктуально категоричных конечнопорожденных структур. Математика и теоретические компьютерные науки. 2023;1(1):69-77.
For citation:
Kurmacheva A.A. On the index set of punctually categorical finitely generated structures. Mathematics and Theoretical Computer Science. 2023;1(1):69-77. (In Russ.)
Просмотров:
134
Послать статью по эл. почте 