Avoiding Abelian powers in binary words with bounded Abelian complexity
| Autor: | Gwénaël Richomme, Julien Cassaigne, Luca Q. Zamboni, Kalle Saari |
|---|---|
| Přispěvatelé: | Institut de mathématiques de Luminy (IML), Université de la Méditerranée - Aix-Marseille 2-Centre National de la Recherche Scientifique (CNRS), Université Paul-Valéry - Montpellier 3 (UPVM), Arithmétique informatique (ARITH), Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM), Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM), Department of Mathematics, University of Turku, Institut Camille Jordan [Villeurbanne] (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Université Jean Monnet [Saint-Étienne] (UJM)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS), Institut Camille Jordan (ICJ), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2010 |
| Předmět: |
FOS: Computer and information sciences
Torsion subgroup Discrete Mathematics (cs.DM) [MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS] Abelian complexity Elementary abelian group 0102 computer and information sciences 68R15 [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM] 01 natural sciences Rank of an abelian group Combinatorics [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] Computer Science (miscellaneous) FOS: Mathematics Mathematics - Combinatorics 0101 mathematics Abelian group Hidden subgroup problem Mathematics Arithmetic of abelian varieties Avoidability in words 010102 general mathematics Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) 16. Peace & justice Free abelian group Abelian power 010201 computation theory & mathematics MSC (2000): 68R15 Abelian category Combinatorics (math.CO) Computer Science::Formal Languages and Automata Theory Computer Science - Discrete Mathematics |
| Zdroj: | International Journal of Foundations of Computer Science International Journal of Foundations of Computer Science, World Scientific Publishing, 2011, 22 (4), pp.905-920. ⟨10.1142/S0129054111008489⟩ International Journal of Foundations of Computer Science, 2011, 22 (4), pp.905-920. ⟨10.1142/S0129054111008489⟩ |
| ISSN: | 0129-0541 |
| DOI: | 10.1142/S0129054111008489⟩ |
| Popis: | The notion of Abelian complexity of infinite words was recently used by the three last authors to investigate various Abelian properties of words. In particular, using van der Waerden's theorem, they proved that if a word avoids Abelian $k$-powers for some integer $k$, then its Abelian complexity is unbounded. This suggests the following question: How frequently do Abelian $k$-powers occur in a word having bounded Abelian complexity? In particular, does every uniformly recurrent word having bounded Abelian complexity begin in an Abelian $k$-power? While this is true for various classes of uniformly recurrent words, including for example the class of all Sturmian words, in this paper we show the existence of uniformly recurrent binary words, having bounded Abelian complexity, which admit an infinite number of suffixes which do not begin in an Abelian square. We also show that the shift orbit closure of any infinite binary overlap-free word contains a word which avoids Abelian cubes in the beginning. We also consider the effect of morphisms on Abelian complexity and show that the morphic image of a word having bounded Abelian complexity has bounded Abelian complexity. Finally, we give an open problem on avoidability of Abelian squares in infinite binary words and show that it is equivalent to a well-known open problem of Pirillo-Varricchio and Halbeisen-Hungerb\"uhler. Comment: 16 pages, submitted |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|