RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. 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.

UDC: 519.11.14

Received: 21.05.2012

Language: English


 English version:
Journal of Mathematical Sciences (New York), 2013, 192:3, 352–358

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024