RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив
Импакт-фактор
Подписка
Правила для авторов
Лицензионный договор
Загрузить рукопись
Историческая справка

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



УМН:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


УМН, 2000, том 55, выпуск 2(332), страницы 3–94 (Mi umn267)  

Эта публикация цитируется в 32 научных статьях (всего в 33 статьях)

Алгоритмические проблемы для групп и полугрупп

С. И. Адянa, В. Г. Дурневb

a Математический институт им. В. А. Стеклова РАН
b Ярославский государственный университет им. П. Г. Демидова

Аннотация: В статье дается подробный обзор результатов по основным алгоритмическим проблемам теории групп и полугрупп: проблемам равенства, изоморфизма, распознавания свойств и другим алгоритмическим вопросам, связанным с этими проблемами. Известные теоремы Маркова–Поста, П. С. Новикова, Адяна–Рабина, Хигмана, Магнуса, Линдона изложены с полными доказательствами. Как правило, приводимые в обзоре доказательства этих теорем существенно проще тех, которые давались авторами теорем в их оригинальных работах. В началe статьи для полноты приводится доказательство результата о неразрешимости проблемы остановки для машин Тьюринга, на котором основывается неразрешимость проблемы равенства для полугрупп. Особое внимание уделено также простейшим примерам полугрупп с неразрешимой проблемой равенства. Подробно изложено доказательство весьма примечательного результата Р. Линдона о разрешимости проблемы равенства в классе групп, задаваемых системой определяющих соотношений с условием, что максимальное взаимное наложение определяющих слов строго меньше $1/5$ длины самих этих слов, в то время как при замене в этом условии строгого неравенства на нестрогое уже возникает возможность неразрешимости. Изложено также доказательство аналогичного результата для конечно определенных полугрупп, где соответствующая точная граница равна $1/2$.
Библиография: 110 названий.

DOI: https://doi.org/10.4213/rm267

Полный текст: PDF файл (665 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Russian Mathematical Surveys, 2000, 55:2, 207–296

Реферативные базы данных:

Тип публикации: Статья
УДК: 510.53+512.53+512.54
MSC: Primary 20F10, 20M05; Secondary 20E06, 03D40, 03D10
Поступила в редакцию: 26.01.2000

Образец цитирования: С. И. Адян, В. Г. Дурнев, “Алгоритмические проблемы для групп и полугрупп”, УМН, 55:2(332) (2000), 3–94; Russian Math. Surveys, 55:2 (2000), 207–296

Цитирование в формате AMSBIB
\RBibitem{AdiDur00}
\by С.~И.~Адян, В.~Г.~Дурнев
\paper Алгоритмические проблемы для групп и полугрупп
\jour УМН
\yr 2000
\vol 55
\issue 2(332)
\pages 3--94
\mathnet{http://mi.mathnet.ru/umn267}
\crossref{https://doi.org/10.4213/rm267}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1779941}
\zmath{https://zbmath.org/?q=an:0958.20029}
\adsnasa{http://adsabs.harvard.edu/cgi-bin/bib_query?2000RuMaS..55..207A}
\transl
\jour Russian Math. Surveys
\yr 2000
\vol 55
\issue 2
\pages 207--296
\crossref{https://doi.org/10.1070/rm2000v055n02ABEH000267}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000089971300001}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-0034415361}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/umn267
  • https://doi.org/10.4213/rm267
  • http://mi.mathnet.ru/rus/umn/v55/i2/p3

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. Karpuz E.G., Ozalan N.U., “Word Problem For Special Braid Groups(1)”, Quaest. Math., 1–27  crossref  isi  scopus
    2. Sossinsky A.B., “Undecidability of the freedom problem for 3-manifold groups”, Russ. J. Math. Phys., 7:4 (2000), 482–487  mathscinet  zmath  isi
    3. В. Ю. Попов, “Марковские свойства бернсайдовских многообразий полугрупп”, Алгебра и логика, 42:1 (2003), 94–106  mathnet  mathscinet  zmath  elib; V. Yu. Popov, “Markov Properties of Burnside Varieties of Semigroups”, Algebra and Logic, 42:1 (2003), 54–60  crossref
    4. С. И. Адян, Ф. Груневальд, Й. Меннике, “О простых кватернионах, соотношениях Гурвица и новой операции расширения групп”, Математическая логика и алгебра, Сборник статей. К 100-летию со дня рождения академика Петра Сергеевича Новикова, Тр. МИАН, 242, Наука, МАИК «Наука/Интерпериодика», М., 2003, 7–22  mathnet  mathscinet  zmath; S. I. Adian, F. Grunevald, J. Mennicke, “On Prime Quaternions, Hurwitz Relations, and a New Operation of Group Extension”, Proc. Steklov Inst. Math., 242 (2003), 3–17
    5. Лексин В.П., Чернавский А.В., “Нераспознаваемость многообразий. К теореме С. П. Новикова о нераспознаваемости сферы $\mathbb S^n$ при $n\ge 5$”, Докл. РАН, 391:4 (2003), 453–455  mathnet  mathscinet  zmath; Leksin V.P., Chernavskii A.V., “Unrecognizability of manifolds. On Novikov's theorem on the unrecognizability of the sphere $\mathbb S^n$ for $n\ge 5$”, Dokl. Math., 68:1 (2003), 89–92  mathscinet  zmath  isi  elib
    6. Kapovich I., Miasnikov A., Schupp P., Shpilrain V., “Generic-case complexity, decision problems in group theory, and random walks”, J. Algebra, 264:2 (2003), 665–694  crossref  mathscinet  zmath  isi  elib  scopus
    7. Bokut L., Fong Y., Shiao L.S., “Grobner-Shirshov bases for algebras, groups, and semigroups”, Proceedings of the Third International Algebra Conference, 2003, 17–32  crossref  mathscinet  zmath  isi
    8. М. А. Штанько, “Теорема А. А. Маркова и алгоритмически нераспознаваемые комбинаторные многообразия”, Изв. РАН. Сер. матем., 68:1 (2004), 207–224  mathnet  crossref  mathscinet  zmath; M. A. Shtan'ko, “Markov's theorem and algorithmically non-recognizable combinatorial manifolds”, Izv. Math., 68:1 (2004), 205–221  crossref  isi
    9. Adian S.I., “Divisibility problem for one relator monoids”, Theoret. Comput. Sci., 339:1 (2005), 3–6  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    10. Kapovich I., Miasnikov A., Schupp P., Shpilrain V., “Average-case complexity and decision problems in group theory”, Adv. Math., 190:2 (2005), 343–359  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    11. Л. Д. Беклемишев, И. Г. Лысёнок, А. А. Мальцев, С. П. Новиков, М. Р. Пентус, А. А. Разборов, А. Л. Семёнов, В. А. Успенский, “Сергей Иванович Адян (к 75-летию со дня рождения)”, УМН, 61:3(369) (2006), 179–191  mathnet  crossref  mathscinet  zmath  adsnasa  elib; L. D. Beklemishev, I. G. Lysenok, A. A. Mal'tsev, S. P. Novikov, M. R. Pentus, A. A. Razborov, A. L. Semenov, V. A. Uspenskii, “Sergei Ivanovich Adian (on his 75th birthday)”, Russian Math. Surveys, 61:3 (2006), 575–588  crossref  isi
    12. Chernavsky A.V., Leksine V.P., “Unrecognizability of manifolds”, Ann. Pure Appl. Logic, 141:3 (2006), 325–335  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    13. Kreuzer M., Myasnikov A., Rosenberger G., Ushakov A., “Quotient tests and Grobner bases”, Combinatorial Group Theory, Discrete Groups, and Number Theory, Contemporary Mathematics Series, 421, 2006, 187–200  crossref  mathscinet  zmath  isi
    14. Borovik A.V., Myasnikov A.G., “Quotient tests and random walks in computational group theory”, Topological and Asymptotic Aspects of Group Theory, Contemporary Mathematics Series, 394, 2006, 31–45  crossref  mathscinet  zmath  isi
    15. Е. Н. Павловский, “Алгоритмическая распознаваемость свойства конечности конечно-определенных систем”, Вестн. НГУ. Сер. матем., мех., информ., 6:4 (2006), 83–92  mathnet
    16. Borovik A.V., Myasnikov A.G., Remeslennikov V.N., “The conjugacy problem in amalgamated products. I. Regular elements and black holes”, Internat. J. Algebra Comput., 17:7 (2007), 1299–1333  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    17. Myasnikov A., “Generic Complexity of Undecidable Problems”, Computer Science - Theory and Applications, Lecture Notes in Computer Science, 4649, eds. Diekert V., Volkov M., Voronkov A., Springer-Verlag Berlin, 2007, 407–417  crossref  zmath  isi
    18. С. И. Адян, “Группы с периодическими определяющими соотношениями”, Матем. заметки, 83:3 (2008), 323–332  mathnet  crossref  mathscinet  zmath; S. I. Adian, “Groups with Periodic Defining Relations”, Math. Notes, 83:3 (2008), 293–300  crossref  isi  elib
    19. Myasnikov A.G., Rybalov A.N., “Generic Complexity of Undecidable Problems”, J. Symb. Log., 73:2 (2008), 656–673  crossref  mathscinet  zmath  isi  elib  scopus  scopus
    20. Cain A.J., Maltcev V., “Decision problems for finitely presented and one-relation semigroups and monoids”, Internat. J. Algebra Comput., 19:6 (2009), 747–770  crossref  mathscinet  zmath  isi  scopus  scopus
    21. Karpuz E.G., Çevik A.S., “The word and generalized word problem for semigroups under wreath products”, Bull. Math. Soc. Sci. Math. Roum., Nouv. Sér., 52:2 (2009), 151–160  zmath  isi
    22. Alexei Myasnikov, Denis Osin, “Algorithmically finite groups”, Journal of Pure and Applied Algebra, 2011  crossref  mathscinet  isi  scopus
    23. Alexei Myasnikov, Alexander Ushakov, “Random van Kampen diagrams and algorithmic problems in groups”, Groups – Complexity – Cryptology, 3:3 (2011), 121  crossref  mathscinet  zmath  scopus
    24. А. Г. Мясников, В. Н. Ремесленников, Е. В. Френкель, “Свободное произведение групп с объединением: нормальные формы и меры”, Матем. заметки, 91:4 (2012), 633–637  mathnet  crossref  mathscinet  elib; A. G. Myasnikov, V. N. Remeslennikov, E. V. Frenkel, “Amalgamated Free Product of Groups: Normal Forms and Measures”, Math. Notes, 91:4 (2012), 592–596  crossref  isi  elib
    25. В. А. Романьков, “Диофантова криптография на бесконечных группах”, ПДМ, 2012, № 2(16), 15–42  mathnet
    26. Э. Г. Карпуз, А. С. Чевик, “Базисы Грёбнера–Ширшова для расширенных модулярных групп, расширенных групп Гекке и групп Пикара”, Матем. заметки, 92:5 (2012), 699–706  mathnet  crossref  mathscinet  zmath  elib; E. G. Karpuz, A. S. Cevik, “Gröbner–Shirshov Bases for Extended modular, Extended Hecke, and Picard Groups”, Math. Notes, 92:5 (2012), 636–642  crossref  isi  elib
    27. В. Н. Безверхний, И. В. Добрынина, “О свободных подгруппах в группах Артина с древесной структурой”, Чебышевский сб., 15:1 (2014), 32–42  mathnet
    28. J.W.. Johnson, “Weight ideals associated to regular and log-linear arrays”, Journal of Symbolic Computation, 2014  crossref  mathscinet  isi  scopus  scopus
    29. В. Г. Дурнев, О. В. Зеткина, “Некоторые результаты, полученные в Ярославском отделении алгебраической школы М. Д. Гриндлингера”, Чебышевский сб., 15:4 (2014), 5–31  mathnet
    30. Karpuz E.G., Ates F., Cevik A.S., “Grobner-Shirshov Bases of Some Weyl Groups”, 45, no. 4, 2015, 1165–1175  crossref  mathscinet  zmath  isi  scopus  scopus
    31. 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  crossref  mathscinet  zmath  isi  elib  scopus
    32. Szabo P., Siekmann J., Hoche M., “What Is Essential Unification?”, Martin Davis on Computability, Computational Logic, and Mathematical Foundations, Outstanding Contributions to Logic, 10, eds. Omodeo E., Policriti A., Springer International Publishing Ag, 2016, 285–314  crossref  mathscinet  isi
    33. 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  crossref  mathscinet  zmath  isi  scopus
  • Успехи математических наук Russian Mathematical Surveys
    Просмотров:
    Эта страница:1361
    Полный текст:463
    Литература:57
    Первая стр.:4
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019