Аннотация:
В статье дается подробный обзор результатов по основным алгоритмическим проблемам теории групп и полугрупп: проблемам равенства, изоморфизма, распознавания свойств и
другим алгоритмическим вопросам, связанным с этими проблемами. Известные теоремы Маркова–Поста, П. С. Новикова, Адяна–Рабина, Хигмана, Магнуса, Линдона
изложены с полными доказательствами. Как правило, приводимые в обзоре доказательства этих теорем существенно проще тех, которые давались авторами теорем в их оригинальных работах. В началe статьи для полноты приводится доказательство результата о неразрешимости проблемы остановки для машин Тьюринга, на котором основывается
неразрешимость проблемы равенства для полугрупп. Особое внимание уделено также простейшим примерам полугрупп с неразрешимой проблемой равенства. Подробно изложено
доказательство весьма примечательного результата Р. Линдона о разрешимости проблемы равенства в классе групп, задаваемых системой определяющих соотношений с условием,
что максимальное взаимное наложение определяющих слов строго меньше 1/5 длины самих этих слов, в то время как при замене в этом условии строгого неравенства на
нестрогое уже возникает возможность неразрешимости. Изложено также доказательство аналогичного результата для конечно определенных полугрупп, где соответствующая точная граница равна 1/2.
Библиография: 110 названий.
Образец цитирования:
С. И. Адян, В. Г. Дурнев, “Алгоритмические проблемы для групп и полугрупп”, УМН, 55:2(332) (2000), 3–94; Russian Math. Surveys, 55:2 (2000), 207–296
Zbigniew Lipiński, Jolanta Mizera-Pietraszko, Jolanta Tańcula, “A Study of Cryptographic Algorithms on Special Linear Group Over Ring of Integers Modulo m”, IEEE Access, 13 (2025), 5606
Eylem Guzel Karpuz, Fatmanur Y{\i}ld{\i}z, “Complete Rewriting System of Schützenberger – Crossed Product of Monoids”, Karamanoğlu Mehmetbey Üniversitesi Mühendislik ve Doğa Bilimleri Dergisi, 6:2 (2024), 33
В. А. Романьков, “Неразрешимость проблемы вхождения в подмоноид свободной нильпотентной группы ступени l⩾2 достаточно большого ранга”, Изв. РАН. Сер. матем., 87:4 (2023), 166–185; V. A. Roman'kov, “Undecidability of the submonoid membership problem for free nilpotent group of class l⩾2 of sufficiently large rank”, Izv. Math., 87:4 (2023), 798–816
A. N. Rybalov, “Generic Complexity of the Word Problem in Some Semigroups”, Algebra Logic, 61:6 (2023), 524
М. Н. Рыбаков, “Сложность проблемы равенства слов в модальных и псевдобулевых алгебрах с малым числом порождающих”, Изв. вузов. Матем., 2022, № 5, 42–60; M. Rybakov, “Computational complexity of the word problem in modal and pseudo-Boolean algebras
with a small number of generators”, Russian Math. (Iz. VUZ), 66:5 (2022), 33–48
V. A. Roman'kov, “Positive elements and sufficient conditions for solvability of the submonoid membership problem for nilpotent groups of class two”, Сиб. электрон. матем. изв., 19:1 (2022), 387–403
И. В. Добрынина, “О подгруппах в группах Артина с древесной структурой”, Чебышевский сб., 23:3 (2022), 118–132
А. Н. Рыбалов, “О генерической сложности проблемы равенства в некоторых полугруппах”, Алгебра и логика, 61:6 (2022), 766–783
Zbigniew Lipiński, Jolanta Mizera-Pietraszko, Lecture Notes in Computer Science, 13758, Intelligent Information and Database Systems, 2022, 643
V. A. Roman'kov, “Algorithmic theory of solvable groups”, ПДМ, 2021, № 52, 16–64
М. Н. Рыбаков, “Сложность проблемы равенства слов в многообразиях модальных алгебр”, Вестник ТвГУ. Серия: Прикладная математика, 2021, № 3, 5–17
Nyberg-Brodda C.-F., “The Word Problem For One-Relation Monoids: a Survey”, Semigr. Forum, 103:2 (2021), 297–355
Karpuz E.G., Ozalan N.U., “Word Problem For Special Braid Groups(1)”, Quaest. Math., 43:7 (2020), 931–957
Cevik A.S., Karpuz E.G., Alsulami H.H., Cetinalp E.K., “A Grobner-Shirshov Basis Over a Special Type of Braid Monoids”, AIMS Math., 5:5 (2020), 4357–4370
Cevik A.S., Albargi A.H., “A Solution of the Word Problem For Braid Groups Via the Complex Reflection Group G(12)”, Filomat, 34:2, SI (2020), 461–467
Rybalov A., Iv International Scientific and Technical Conference Mechanical Science and Technology Update (Mstu-2020), Journal of Physics Conference Series, 1546, IOP Publishing Ltd, 2020
Cetinalp E.K., Karpuz E.G., Cevik A.S., “Complete Rewriting System For the Schutzenberger Product of N Groups”, Asian-Eur. J. Math., 12:1 (2019), 1950012
Ozalan N.U., Wazzan S.A., Karpuz E.G., “Grobner-Shirshov Bases For Congruence Classes of Complex Reflection Groups”, Asian-Eur. J. Math., 12:6, SI (2019), 2040013
Cetinalp E.K., Karpuz E.G., Sahin R., Ates F., “Complete Rewriting System and Growth Series For Extended Generalized Hecke Groups”, J. Math. Ext., 13:4 (2019), 41–55
Karpuz E.G., Ates F., Urlu N., Cevik A.S., Cangul I.N., “A note on the Gröbner-Shirshov bases over ad-hoc extensions of groups”, Filomat, 30:4 (2016), 1037–1043
Цитирование в формате AMSBIB
Обратная связь: