|
Быстрые алгоритмы для считающих функций на свободных группах и свободных моноидах
А. Л. Таламбуцаa, Т. Хартникb a Математический институт им. В. А. Стеклова Российской академии наук, г. Москва
b Institut für Algebra und Geometrie, Karlsruher Institut für Technologie, Karlsruhe, Germany
Аннотация:
В работе строятся эффективные алгоритмы для проверки, находятся ли две данные считающие функции на неабелевых свободных группах (или моноидах) на ограниченном расстоянии друг от друга, и для проверки, являются ли два данных считающих квазиморфизма на свободных неабелевых группах когомологичными. В качестве модели вычисления нами рассматривается многоленточная машина Тьюринга, для которой арифметические операции не считаются выполнимыми за постоянное время. В случае целочисленных коэффициентов мы строим линейный по времени алгоритм (предполагая, что в случае свободного моноида его ранг не меньше $3$). Для случая рациональных коэффициентов мы доказываем, что временная сложность равна $O(N\log N)$, где $N$ – размер входа, т.е. совпадает со сложностью сложения рациональных чисел (реализованного с помощью алгоритма Харви–ван дер Хувена для умножения целых чисел). Построенные алгоритмы основаны на нашей предыдущей работе, которая дает описание пространства ограниченных считающих функций.
Библиография: 20 названий.
Ключевые слова:
свободный моноид, свободная группа, квазиморфизм, квазихарактер, считающая функция, ограниченные когомологии.
Поступила в редакцию: 28.10.2021 и 17.07.2023
Образец цитирования:
А. Л. Таламбуца, Т. Хартник, “Быстрые алгоритмы для считающих функций на свободных группах и свободных моноидах”, Матем. сб., 214:10 (2023), 116–162; A. L. Talambutsa, T. Hartnick, “Efficient computations with counting functions on free groups and free monoids”, Sb. Math., 214:10 (2023), 1458–1499
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/sm9683https://doi.org/10.4213/sm9683 https://www.mathnet.ru/rus/sm/v214/i10/p116
|
Статистика просмотров: |
Страница аннотации: | 344 | PDF русской версии: | 15 | PDF английской версии: | 35 | HTML русской версии: | 69 | HTML английской версии: | 70 | Список литературы: | 27 | Первая страница: | 8 |
|