A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Problems in between words and abelian words: k-abelian avoidability
Tekijät: Huova M, Karhumaki J, Saarela A
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2012
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 454
Aloitussivu: 172
Lopetussivu: 177
Sivujen määrä: 6
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2012.03.010
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali