О генерической сложности проблемы вхождения для полугрупп целочисленных матриц

doi:10.17223/20710410/55/7

Эндаумент фонд ТГУ!
Впиши своё имя в историю университета
- Сделать пожертвование -

Add to "Quick Collection"

Description	Size	Format
О генерической сложности проблемы вхождения для полугрупп целочисленных матриц	688 KB	Adobe Acrobat PDF	Read	Download
DOI Доступ к ресурсу на сайте издателя			10.17223/20710410/55/7

#генерическая сложность

#проблема вхождения

#полугруппы целочисленных матриц

Title: О генерической сложности проблемы вхождения для полугрупп целочисленных матриц
Title: Generic complexity of the membership problem for semigroups of integer matrices
Creator: Рыбалов, Александр Николаевич
Date: 2022
DOI: 10.17223/20710410/55/7
Description: Проблема вхождения в конечно порождённую подгруппу (подполугруппу) для групп (полугрупп) является классической алгоритмической проблемой в алгебре, активно изучаемой многие десятилетия. Уже для достаточно простых групп и полугрупп эта проблема становится неразрешимой. Например, К. А. Михайлова в 1966 г. доказала неразрешимость проблемы вхождения в конечно порождённые подгруппы и, следовательно, подполугруппы для прямого произведения F2xF2 двух свободных групп ранга 2. Так как по известной теореме Санова группа F2 имеет точное представление целочисленными матрицами порядка 2, группа F2xF2 является подгруппой группы GL4(Z) целочисленных матриц порядка 4. Отсюда легко следует неразрешимость рассматриваемой проблемы для группы GLk(Z) при k > 4. Неразрешимость проблемы вхождения в подполугруппы полугрупп целочисленных матриц порядка > 3 следует из результата М. Патерсона 1970 г. В данной работе предлагается сильно генерический алгоритм, решающий проблему вхождения в подполугруппы полугрупп целочисленных матриц произвольного порядка для подмножества входов, последовательность относительных плотностей которого при увеличении размера экспоненциально быстро сходится к 1.

Relationships: Show Relationship Browser for this Object
collection(s): Журналы ТГУ
Identifier: смотреть в электронном каталоге НБ ТГУ
Type: статьи в журналах
Source: Прикладная дискретная математика. 2022. № 55. С. 95-101
Language: rus

Created: 16-03-2022

359 Visitors

255 Hits

109 Downloads

Журналы ТГУ О генерической сложности проблемы вхождения для полугрупп целочисленных матриц