More Web Proxy on the site http://driver.im/

research-article

On k-abelian palindromes

Authors:

Julien Cassaigne,

Juhani Karhumki,

Svetlana PuzyninaAuthors Info & Claims

Information and Computation, Volume 260, Issue C

Pages 89 - 98

https://doi.org/10.1016/j.ic.2018.04.001

Published: 01 June 2018 Publication History

Abstract

A word is called a palindrome if it is equal to its reversal. In the paper we consider a k-abelian modification of this notion. Two words are called k-abelian equivalent if they contain the same number of occurrences of each factor of length at most k. We say that a word is a k-abelian palindrome if it is k-abelian equivalent to its reversal. A question we deal with is the following: how many distinct palindromes can a word contain? It is well known that a word of length n can contain at most n+1 distinct palindromes as its factors; such words are called rich. On the other hand, there exist infinite words containing only finitely many distinct palindromes as their factors; such words are called poor. We show that in the k-abelian case there exist infinite words containing finitely many distinct k-abelian palindromic factors. For rich words we show that there exist finite words of length n containing (n2) distinct k-abelian palindromes as their factors.

References

[1]

B. Adamczewski, Balances for fixed points of primitive substitutions, Theor. Comput. Sci., 307 (2003) 47-75.

Digital Library

[2]

J.-P. Allouche, M. Baake, J. Cassaigne, D. Damanik, Palindrome complexity, Theor. Comput. Sci., 292 (2003) 9-31.

Digital Library

[3]

J.-P. Allouche, J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, Cambridge, UK, 2003.

Digital Library

[4]

P. Ambro, C. Frougny, Z. Maskov, E. Pelantov, Palindromic complexity of infinite words associated with simple Parry numbers, Ann. Inst. Fourier (Grenoble), 56 (2006) 2131-2160.

[5]

S. Avgustinovich, J. Karhumki, S. Puzynina, On abelian versions of Critical Factorization Theorem, RAIRO Theor. Inform. Appl., 46 (2012) 3-15.

[6]

S. Avgustinovich, S. Puzynina, Weak abelian periodicity of infinite words, Theory Comput. Syst., 59 (2016) 161-179.

Digital Library

[7]

H. Bannai, T. Shunsuke, I. Nakashima, M. Takeda, K. Tsuruta, The runs theorem, SIAM J. Comput., 46 (2017) 1501-1514.

[8]

J. Berstel, L. Boasson, O. Carton, I. Fagnot, Infinite words without palindrome. arXiv:0903.2382

[9]

S. Brlek, S. Hamel, M. Nivat, C. Reutenauer, On the palindromic complexity of infinite words, Int. J. Found. Comput. Sci., 15 (2004) 293-306.

[10]

M. Bucci, A. De Luca, A. Glen, L.Q. Zamboni, A new characteristic property of rich words, Theor. Comput. Sci., 410 (2009) 2860-2863.

Digital Library

[11]

M. Crochemore, L. Ilie, L. Tinta, The runs conjecture, Theor. Comput. Sci., 412 (2011) 2931-2941.

Digital Library

[12]

D. Damanik, D. Zare, Palindrome complexity bounds for primitive substitution sequences, Discrete Math., 222 (2000) 259-267.

Digital Library

[13]

A. de Luca, Sturmian words: structures, combinatorics and their arithmetics, Theor. Comput. Sci., 183 (1997) 45-82.

Digital Library

[14]

X. Droubay, J. Justin, G. Pirillo, Episturmian words and some constructions of de Luca and Rauzy, Theor. Comput. Sci., 255 (2001) 539-553.

[15]

G. Fici, L.Q. Zamboni, On the least number of palindromes contained in an infinite word, Theor. Comput. Sci., 481 (2013) 1-8.

Digital Library

[16]

A. Glen, J. Justin, S. Widmer, L.Q. Zamboni, Palindromic richness, Eur. J. Comb., 30 (2009) 510-531.

Digital Library

[17]

T. Harju, T. Krki, D. Nowotka, The number of positions starting a square in binary words, Electron. J. Comb., 18 (2011).

[18]

L. Ilie, A note on the number of squares in a word, Theor. Comput. Sci., 380 (2007) 373-376.

Digital Library

[19]

J. Karhumki, S. Puzynina, On k-abelian palindromic rich and poor words, in: LNCS, vol. 8633, 2014, pp. 191-202.

[20]

J. Karhumki, S. Puzynina, A. Saarela, Fine and Wilf's theorem for k-Abelian periods, Int. J. Found. Comput. Sci., 24 (2013) 1135-1152.

[21]

J. Karhumki, A. Saarela, L.Q. Zamboni, On a generalization of Abelian equivalence and complexity of infinite words, J. Comb. Theory, Ser. A, 120 (2013) 2189-2206.

Digital Library

[22]

V. Kernen, Abelian squares are avoidable on 4 letters, in: LNCS, vol. 623, Springer, Heidelberg, 1992, pp. 41-52.

[23]

R. Kolpakov, G. Kucherov, Finding maximal repetitions in a word in linear time, in: FOCS, 1999, pp. 596-604.

Digital Library

[24]

G. Kucherov, P. Ochem, M. Rao, How many square occurrences must a binary sequence contain?, Electron. J. Comb., 10 (2003).

[25]

M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, Cambridge, UK, 2002.

[26]

S. Puzynina, L.Q. Zamboni, Abelian returns in Sturmian words, J. Comb. Theory, Ser. A, 120 (2013) 390-408.

Digital Library

[27]

N. Rampersad, J. Shallit, Words avoiding reversed subwords, J. Comb. Math. Comb. Comput., 54 (2005) 157-164.

[28]

G. Richomme, K. Saari, L.Q. Zamboni, Abelian complexity of minimal subshifts, J. Lond. Math. Soc., 83 (2011) 79-95.

[29]

M. Rigo, P. Salimov, Another generalization of abelian equivalence: binomial complexity of infinite words, in: LNCS, vol. 8079, 2013, pp. 217-228.

Cited By

Rigo MStipulanti MWhiteland M(2024)Characterizations of families of morphisms and words via binomial complexitiesEuropean Journal of Combinatorics10.1016/j.ejc.2024.103932118:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.ejc.2024.103932
Parshina OPuzynina S(2021)On Closed-Rich WordsComputer Science – Theory and Applications10.1007/978-3-030-79416-3_23(381-394)Online publication date: 28-Jun-2021
https://dl.acm.org/doi/10.1007/978-3-030-79416-3_23
Avgustinovich SCassaigne JKarhumäki JPuzynina SSaarela A(2019)On abelian saturated infinite wordsTheoretical Computer Science10.1016/j.tcs.2018.05.013792:C(154-160)Online publication date: 5-Nov-2019
https://dl.acm.org/doi/10.1016/j.tcs.2018.05.013

On k-abelian palindromes
1. Mathematics of computing
  1. Discrete mathematics
    1. Combinatorics
2. Theory of computation

Recommendations

On the number of episturmian palindromes

Episturmian words are a suitable generalization to arbitrary alphabets of Sturmian words. In this paper we are interested in the problem of enumerating the palindromes in all episturmian words over a k-letter alphabet A"k. We give a formula for the map ...
Palindromes in circular words

There is a very short and beautiful proof that the number of distinct non-empty palindromes in a word of length n is at most n. In this paper we show, with a very complicated proof, that the number of distinct non-empty palindromes with length at most n ...
Enumeration and structure of trapezoidal words

Trapezoidal words are words having at most n+1 distinct factors of length n for every n>=0. They therefore encompass finite Sturmian words. We give combinatorial characterizations of trapezoidal words and exhibit a formula for their enumeration. We then ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information and Computation

Information and Computation Volume 260, Issue C

June 2018

134 pages

ISSN:0890-5401

Issue’s Table of Contents

Copyright © Elsevier Inc.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 June 2018

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Rigo MStipulanti MWhiteland M(2024)Characterizations of families of morphisms and words via binomial complexitiesEuropean Journal of Combinatorics10.1016/j.ejc.2024.103932118:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.ejc.2024.103932
Parshina OPuzynina S(2021)On Closed-Rich WordsComputer Science – Theory and Applications10.1007/978-3-030-79416-3_23(381-394)Online publication date: 28-Jun-2021
https://dl.acm.org/doi/10.1007/978-3-030-79416-3_23
Avgustinovich SCassaigne JKarhumäki JPuzynina SSaarela A(2019)On abelian saturated infinite wordsTheoretical Computer Science10.1016/j.tcs.2018.05.013792:C(154-160)Online publication date: 5-Nov-2019
https://dl.acm.org/doi/10.1016/j.tcs.2018.05.013

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents