Комбинаторные свойства бернсайдовых полугрупп

Свободной бернсайдовой полугруппой B(k,n,n+m) называется относительно свободная полугруппа ранга k с тождеством, устанавливающим равенство n-ой степени любого слова над алфавитом свободных порождающих (n+m)-ой степени того же слова. Элементами таких полугрупп являются классы эквивалентных слов. Важнейшей алгоритмической проблемой теории бернсайдовых полугрупп является проблема равенства слов: по двум заданным словам над алфавитом свободных порождающих определить, представляют ли эти слова один и тот же элемент данной полугруппы. В 1969 году Бжозовским была сформулирована гипотеза о том, что всякий элемент свободной бернсайдовой полугруппы является рациональным языком. В книге исследуются полугруппы B(k,2,3), так как для них обе рассматриваемые проблемы остаются открытыми. Доказывается сводимость обеих проблем для произвольной полугруппы B(k,2,3) к полугруппе B(2,2,3) ранга 2, а также дается частичное решение проблемы равенства слов для полугруппы B(2,2,3). Книга адресована специалистам по теории полугрупп, теории формальных языков и комбинаторики слов.