
Коллектив автоматов в конечно-порожденных группах
Author(s) -
D. V. Gusev,
Daniel Vladimirovich Gusev,
Ilya Ivanov-Pogodaev,
Ilya Ivanov-Pogodaev,
Алексей Яковлевич Канель-Белов,
Alexei Kanel-Belov
Publication year - 2020
Publication title -
matematičeskie zametki
Language(s) - Russian
Resource type - Journals
eISSN - 2305-2880
pISSN - 0025-567X
DOI - 10.4213/mzm12898
Subject(s) - geography
Данная работа посвящена обхождению лабиринтаколлективом конечных автоматов. Эта часть теории автоматов породиладовольно широкий спектр различных задач [1], [2],в том числе связанных с задачами теории сложности вычислений итеорией вероятностей. Оказывается,что рассмотрение сложных алгебраических объектов,таких как бернсайдовы группы, может быть интереснымв данном контексте. В работе будет показано, что граф Кэликонечно-порожденной группы нельзя обойти коллективом автоматовтогда и только тогда, когда она бесконечна икаждый ее элемент периодичен.Библиография: 18 названий.