|
Zapiski Nauchnykh Seminarov POMI, 2012, Volume 402, Pages 170–182
(Mi znsl5243)
|
|
|
|
On $k$-abelian avoidability
M. Huova, J. Karhumäki Department of Mathematics and TUCS, University of Turku, Turku, Finland
Abstract:
We consider a recently defined notion of $k$-abelian equivalence of words by giving some basic results and concentrating on avoidability problems. This equivalence relation counts the numbers of factors of length $k$ for a fixed natural number $k$. We ask for the size of the smallest alphabet for which $k$-abelian squares and cubes can be avoided, respectively. For $2$-abelian squares this is four – as in the case of abelian words, while for $2$-abelian cubes we have only strong evidence that the size is two – as it is in the case of words. In addition, we point out a few properties of morphisms supporting the view that it might be difficult to find solutions to our questions by simply iterating a morphism.
Key words and phrases:
combinatorics on words, $k$-abelian equivalence, avoidability.
Received: 21.05.2012
Citation:
M. Huova, J. Karhumäki, “On $k$-abelian avoidability”, Combinatorics and graph theory. Part IV, RuFiDiM'11, Zap. Nauchn. Sem. POMI, 402, POMI, St. Petersburg, 2012, 170–182; J. Math. Sci. (N. Y.), 192:3 (2013), 352–358
Linking options:
https://www.mathnet.ru/eng/znsl5243 https://www.mathnet.ru/eng/znsl/v402/p170
|
Statistics & downloads: |
Abstract page: | 135 | Full-text PDF : | 33 | References: | 36 |
|