On $k$-abelian avoidability
[О
$k$-абелевой избегаемости]
M. Huova,
J. Karhumäki Department of Mathematics and TUCS, University of Turku, Turku, Finland
Аннотация:
Мы изучаем недавно введенное поняти
$k$-абелевой эквивалентности слов, приводим его некоторые основные свойства, и концентрирумся на проблеме избегаемости. Это отношение эквивалентности считает количество подслов длины
$k$ для фиксированного натурального числа
$k$. Мы интересуемся размером наименьшего алфавита, в котором можно избежать
$k$-абелевых квадратов и кубов соответственно. Для
$2$-абелевых квадратов этот размер равен четырём – аналогично случаю
абелевых слов, в то время как для
$2$-абелевых кубов мы имеем только сильное свидетельство в пользу того, что этот размер равен двум – аналогично случаю
слов. Кроме того, мы указываем несколько свойств морфизмов, которые показывают, что было бы трудно найти ответы на наши вопросы путем простого итерирования морфизмов. Библ. – 17 назв.
Ключевые слова:
комбинаторика слов,
$k$-абелева эквивалентность, избегаемость.
УДК:
519.11.14
Поступило: 21.05.2012
Язык публикации: английский