On \(k\)-abelian palindromes
type: Item
instance of: scholarly article
title: On \(k\)-abelian palindromes
zbMATH Open document ID: 1393.68138
author: Julien Cassaigne
author: Juhani Karhumäki
author: Svetlana Puzynina
published in: Information and Computation
publication date: 2018-05-30T00:00:00Z
review text: A finite word is called a \textit{palindrome} if it is equal to its reversal, that is, if it is the same when read from left to right or from right to left. It is well known that a finite word of length \(n\) can contain at most \(n+1\) distinct palindromes as its factors. Finite words having the maximal number of distinct factors that are palindromes are called \textit{rich}. Similarly, an infinite rich word is a word such that each of its factors is rich. On the other hand, infinite words containing only finitely many distinct palindroms as their factors are called \textit{poor}. It is known that there exist poor words even when the set of factors is closed under reversal. In this paper the authors consider a \(k\)-abelian modification of these notions. Two words are called \(k\)-\textit{abelian equivalent} if they contain the same number of occurrences of each factor of length at most \(k\). Thus, the classical notion of abelian equivalence corresponds to \(1\)-abelian equivalence. A word is a \(k\)-\textit{abelian palindrome} if it is \(k\)-abelian equivalent to its reversal. In this paper the authors deal with the question: how many distinct \(k\)-palindromes can a (finite or infinite) word contain? A \(k\)-\textit{abelian palindromic poor word} is defined as an infinite word containing only finitely many \(k\)-abelian palindromes. One of the main results of the paper is a complete classification of the pairs \((k, \ell)\), for existence of \(k\)-poor words for an alphabet of cardinality \(\ell\). It is shown that: -- for \(k=1\) and for the pairs \((2,2), (3,2)\) it is not possible to have \(k\)-abelian palindromic poor words; -- for the pairs \((2,3), (4,2)\) there exist \(k\)-abelian poor words, but there are no \(k\)-abelian palindromic poor words having a set of factors closed under \(k\)-abelian reversal; -- for all the other cases it is possible to construct uniformly recurrent \(k\)-abelian palindromic poor words having a set of factors that is closed u…
reviewed by: Francesco Dolce
Mathematics Subject Classification ID: 68R15
zbMATH DE Number: 6876405
zbMATH Keywords: infinite words
zbMATH Keywords: palindromes
zbMATH Keywords: rich words
zbMATH Keywords: \(k\)-abelian equivalence
MaRDI profile type: Publication
full work available at URL: j.ic.2018.04.001
OpenAlex ID: W2795583685
cites work: Balances for fixed points of primitive substitutions.
cites work: Palindrome complexity.
cites work: Automatic Sequences
cites work: Palindromic complexity of infinite words associated with simple Parry numbers
cites work: On abelian versions of critical factorization theorem
cites work: Weak abelian periodicity of infinite words
cites work: The “Runs” Theorem
cites work: ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
cites work: A new characteristic property of rich words
cites work: The ``runs'' conjecture
cites work: Palindrome complexity bounds for primitive substitution sequences
cites work: Sturmian words: structure, combinatorics, and their arithmetics
cites work: Episturmian words and some constructions of de Luca and Rauzy
cites work: On the least number of palindromes contained in an infinite word
cites work: Palindromic richness
cites work: The number of positions starting a square in binary words
cites work: A note on the number of squares in a word
cites work: On k-Abelian Palindromic Rich and Poor Words
cites work: FINE AND WILF'S THEOREM FOR k-ABELIAN PERIODS
cites work: On a generalization of abelian equivalence and complexity of infinite words
cites work: Abelian squares are avoidable on 4 letters
cites work: How many square occurrences must a binary sequence contain?
cites work: Q4529547
cites work: Abelian returns in Sturmian words
cites work: Q5710443
cites work: Abelian complexity of minimal subshifts
cites work: Another Generalization of Abelian Equivalence: Binomial Complexity of Infinite Words
DOI: 10.1016/J.IC.2018.04.001
description: scientific article; zbMATH DE number 6876405