A1 Refereed original research article in a scientific journal
Problems in between words and abelian words: k-abelian avoidability
Authors: Huova M, Karhumaki J, Saarela A
Publisher: ELSEVIER SCIENCE BV
Publication year: 2012
Journal: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 454
First page : 172
Last page: 177
Number of pages: 6
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2012.03.010
Abstract
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.
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.
UTU Research Portal