Алгоритми для розв"язання проблеми рівності в групах та напівгрупах (асинхронних) автоматних перетворень. Доведення ізоморфізма груп асинхронно автоматних перетворень над різними алфавітами. Розв"язання проблеми Григорчука про класифікацію груп Gw.
Аннотация к работе
КИЇВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ АВТОРЕФЕРАТ дисертації на здобуття наукового ступеня доктора фізико-математичних наукНауковий консультант: СУЩАНСЬКИЙ Віталій Іванович, доктор фізико-математичних наук, професор. Офіційні опоненти: НОВІКОВ Борис Володимирович, доктор фіз.-мат. наук, професор, Харківський національний університет ім. САМОЙЛЕНКО Юрій Стефанович, доктор фіз.-мат. наук, професор, член-кореспондент НАН України, Інститут математики НАН України, завідувач відділу функціонального аналізу; УСТИМЕНКО Василь Олександрович, доктор фіз.-мат. наук, професор, Національний університет, "Києво-Могилянська Академія", кафедра математики.Самоподібні (станово-замкнені) групи зявляються природньо при дослідженні груп автоматних підстановок. Група, що діє на дереві X називається самоподібною, якщо дія кожного елемента g групи на довільному піддереві VX збігається із дією якогось елемента цієї ж групи. Пізніше почали вивчатися аналоги групи Григорчука та розроблятися техніка для вивчення таких груп. Тут варто згадати групи Гупти-Сідкі, групу Браннера-Сідкі-Вієйри та групу описану Р.Григорчуком та А.Жуком у статті. Групи, породжені автоматами: Побудовано алгоритми для розвязання проблеми рівності в групах та напівгрупах (асинхронних) автоматних перетворень.Крім того, доводиться, що група та напівгрупа скінченних асинхронних автоматів не залежать від розміру скінченного алфавіту, над яким вони визначені (Теорема 2.33). Шостий підрозділ другого розділу вивчає групи, породжені синхронними автоматами з точки зору їх дій на кореневому дереві скінченних слів. Крім цього означення, самоподібні групи можна визначати в термінах теорії автоматів (як синхронний автомат, множина станів якого є групою та як групу, породжену автоматом) та за допомогою вінцевих рекурсій. У кінці першого підрозділу розглядаються класичні приклади самоподібних груп (група Григорчука, групи Гупти-Сідкі, група Гупти-Фабриковського, група Браннера-Сідкі-Вієйри, група >, самоподібна дія вільної групи та стабілізатори вершини в транзитивних діях на графах). Віртуальним ендоморфізмом групи G називається гомоморфізм із підгрупи скінченного індексу групи G у групу G.---Побудовано алгоритми для обчислень із асинхронними автоматами та алгоритми для розвязання проблеми рівності у групах та напівгрупах, породжених автоматами. Доведено, що група скінченних асинхронних автоматів не залежить від розміру алфавіту над яким визначаються автомати. ---Побудовано алгебраїчну теорію самоподібності груп. Розроблено техніку для роботи із самоподібними групами: віртуальні ендоморфізми та підстановкові бімодулі. Доведено, що проблема рівності у стискуючих групах має поліноміальну складність та розроблено ефективний алгоритм для розвязання проблеми слів у таких групах.