Конечно порождённые структуры, вычислимые за полиномиальное время | Sciact - Система учета научной деятельности ИМ СО РАН

Конечно порождённые структуры, вычислимые за полиномиальное время Научная публикация

Журнал

Сибирский математический журнал
ISSN: 0037-4474

Вых. Данные

Год: 2022, Том: 63, Номер: 5, Страницы: 953-974 Страниц : 22 DOI: 10.33048/smzh.2022.63.501

Авторы

Алаев П.Е. ¹

Организации

1	Институт математики им. С. Л. Соболева СО РАН, пр. Академика Коптюга, 4, Новосибирск 630090

Информация о финансировании (2)

1	Институт математики им. С.Л. Соболева СО РАН	FWNF-2022-0011
2	Российский фонд фундаментальных исследований	20-01-00300

Получено простое описание конечно порождённых структур, обладающих изоморфным представлением, вычислимым за полиномиальное время (P-вычислимых). Описание близко к формулировке теоремы Дж. Реммела и Х. Фридмана. Доказано, что любая конечно порождённая подструктура P-вычислимой структуры также обладает P-вычислимым представлением. Полученное описание применяется к классам конечно порождённых полугрупп, групп, коммутативных колец с единицей и полей, а также упорядоченных коммутативных колец с единицей и полей. Доказано, что любое конечно порождённое коммутативное кольцо или поле обладают P-вычислимым представлением.

Алаев П.Е.
Конечно порождённые структуры, вычислимые за полиномиальное время
Сибирский математический журнал. 2022. Т.63. №5. С.953-974. DOI: 10.33048/smzh.2022.63.501 РИНЦ

Alaev P.E.
Finitely generated structures computable in polynomial time
Siberian Mathematical Journal. 2022. V.63. N5. P.801-818. DOI: 10.1134/S0037446622050019 WOS Scopus РИНЦ OpenAlex

РИНЦ:

50514925

БД	Цитирований
РИНЦ	3