"Записки научных семинаров ПОМИ"
Том 402, стр. 170-182
О $k$-абелевой избегаемости
М. Хуова, Ю. Кархюмяки
Department of Mathematics
and Turku Centre for Computer Science (TUCS),
University of Turku,
FIN-20014 Turku,
Finland
mari.huova@utu.fi, karhumak@utu.fi
- Аннотация: Мы изучаем недавно введенное понятие
\textit{$k$-абелевой эквивалентности} слов, приводим
его некоторые основные свойства,
и концентрирумся на проблеме избегаемости.
Это отношение эквивалентности считает количество
подслов длины
$k$ для фиксированного натурального числа $k$.
Мы интересуемся размером наименьшего алфавита,
в котором можно избежать $k$-абелевых квадратов и
кубов соответственно. Для 2-абелевых квадратов этот размер
равен четырём -- аналогично случаю \textit{абелевых слов},
в то время как для 2-абелевых кубов мы имеем только
сильное свидетельство в пользу того, что этот размер равен
двум -- аналогично случаю \textit{слов}.
Кроме того, мы указываем несколько свойств морфизмов,
которые показывают, что было бы трудно найти ответы на
наши вопросы путем простого итерирования морфизмов.
Библ. -- 17 назв.
- Ключевые слова: комбинаторика слов, $k$-абелева эквивалентность, избегаемость [combinatorics on words,
k-abelian equivalence, avoidability]
Полный текст(.pdf)