Problems in between words and abelian words: k-abelian avoidability



: Huova M, Karhumaki J, Saarela A

Publisher: ELSEVIER SCIENCE BV

: 2012

: Theoretical Computer Science

: THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 454

: 172

: 177

: 6

: 0304-3975

DOI: https://doi.org/10.1016/j.tcs.2012.03.010


We consider a recently defined notion of k-abelian equivalence of words in connection with avoidability problems. This equivalence relation, for a fixed natural number k, takes into account the numbers of occurrences of the different factors of length k and the prefix and the suffix of length k - 1. We search for the smallest alphabet in 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. However, we are able to prove this optimal value only for 8-abelian cubes. (C) 2012 Elsevier B.V. All rights reserved.



Last updated on 2024-26-11 at 21:56