Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
On k-abelian palindromes
Cassaigne J., Karhumki J., Puzynina S. Information and Computation260 (C):89-98,2018.Type:Article
Date Reviewed: Oct 17 2018

This paper explores words (finite strings over a fixed finite alphabet Σ with at least two letters) that are k-abelian equivalent to their reversals. Two words are k-abelian equivalent if and only if their multisets of factors of length no greater than k are the same. Thus aaba and abaa are 2-equivalent with factors {ε, a(3), b, aa, ab, ba}, but not 3-equivalent. That means aaba is a 2-abelian palindrome, but not a 3-abelian palindrome. (Note that the empty word ε is always a factor--and a palindrome.) On the other hand, baba is not a 2-palindrome, although it is a 1-palindrome (every word is). A real palindrome is a k-palindrome for all k.

The authors extend known counting results for palindromes to k-palindromes. One of the elegant tools is a non-self-intersecting fractal path defined by word substitution. It is used to specify, for all k ≥ 2 (except when k = 2 or 3 and |Σ| = 2), an infinite sequence with only finitely many distinct k-palindromes among its factors (finite subwords). For ordinary palindromes, such sequences are called “poor.” Thus, there are analogous k-poor sequences for k-palindromes. Actually, (abc)ω is ≥2-poor trivially, with only four ≥2-palindromes: ε, a, b, c. The authors’ results are far more technically nuanced. For example, if k ≥ 3 and |Σ| ≥ 3, then there is a uniformly recurrent (every factor occurs infinitely often with bounded gaps between) k-poor sequence whose factors are closed under reversal.

The other principal result is analogous for rich words. A word of length n can have no more than n+1 distinct palindromic factors, and the limit is strict; words with n+1 palindromic factors are called “rich.” In the case of k-palindromes, a word of length n contains at most 1+n(n+1)/2 factors total, so a k-abelian rich word of length n cannot contain more than Θ(n2) k-palindromes. The authors prove that there are k-rich words with at least that many: for all k ≥ 2, there is a positive constant C such that for each nk there exists a word v of length n containing at least Cn2 k-palindromes. In fact, C can be taken as 1/(4k). The word sought is constructed as v = ap(bak-1)m, where m is the closest integer to (n-k+1)/(2k) and p = n-km.

There are minor errors: at the end of line 8b on page 93, (4,2) should be (2,4). Occurrences of the superscript ∞ should be changed to ω for uniformity.

For the most part, the exposition is abundantly clear, and the rest just takes some satisfying rereading. There are more jewels like the ones mentioned, and this is an important contribution to the growing interest and development in counting palindromes and similar issues.

Reviewer:  Benjamin Wells Review #: CR146284 (1902-0036)
Bookmark and Share
  Featured Reviewer  
 
Nonnumerical Algorithms And Problems (F.2.2 )
 
 
Combinatorics (G.2.1 )
 
Would you recommend this review?
yes
no
Other reviews under "Nonnumerical Algorithms And Problems": Date
Improving the performance guarantee for approximate graph coloring
Wigderson A. Journal of the ACM 30(4): 729-735, 1983. Type: Article
Feb 1 1985
Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebra
Demel J., Demlová M., Koubek V. Theoretical Computer Science 36(2-3): 203-216, 1985. Type: Article
Jan 1 1986
Complexity of the word problem for commutative semigroups of fixed dimension
Huynh D. Acta Informatica 22(4): 421-432, 1985. Type: Article
May 1 1986
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy