SCI Библиотека

В монографии представлены основные элементы классической теории регулярных подмножеств (языков) свободных моноидов. Главная цель монографии состоит в изложении теории объектов более широкого класса - рациональных подмножеств произвольных моноидов, в частности групп. Даны основные свойства рациональных подмножеств. Рассмотрены рациональные подмножества свободных и свободных абелевых групп. Изучен вопрос о том, в каких группах рациональные подмножества образуют булеву алгебру. Исследованы алгоритмические проблемы, связанные с рациональными подмножествами. Вычислены асимптотические плотности рациональных подмножеств свободных абелевых групп. Доказано, что собственные нетривиальные вербальные подмножества свободных неабелевых групп нерациональны. В заключение приводится краткий обзор ряда других результатов. Монография адресована специалистам по теории групп и теории формальных языков. Может быть полезной для студентов, магистрантов и аспирантов, изучающих эти предметы, а также для преподавателей соответствующих курсов.