Another Generalization of Abelian Equivalence: Binomial Complexity of Infinite Words

Rigo, Michel; Salimov, Pavel

doi:10.1007/978-3-642-40579-2_23

Download

Paper published in a journal (Scientific congresses and symposiums)

Another Generalization of Abelian Equivalence: Binomial Complexity of Infinite Words

Rigo, Michel; Salimov, Pavel

2013 • In Lecture Notes in Computer Science, 8079, p. 217-228

Peer reviewed

Permalink
https://hdl.handle.net/2268/149313

DOI
10.1007/978-3-642-40579-2_23

Files (2)Send to Details Statistics Bibliography Similar publications

Files

Full Text

binomial_final_short.pdf

Author preprint (178.84 kB)

Download

Annexes

binomial_final_long.pdf

(273.21 kB)

Long version with ommitted proofs

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Sturmian word; Thue-Morse word; Abelian complexity; Combinatorics on words; Binomial coefficient

Abstract :

[en] The binomial coefficient of two words u and v is the number of times v occurs as a subsequence of u. Based on this classical notion, we introduce the m-binomial equivalence of two words refining the abelian equivalence. The m-binomial complexity of an infinite word x maps an integer n to the number of m-binomial equivalence classes of factors of length n occurring in x. We study the first properties of m-binomial equivalence. We compute the m-binomial complexity of the Sturmian words and of the Thue-Morse word. We also mention the possible avoidance of 2-binomial squares.

Disciplines :

Mathematics

Author, co-author :

Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Salimov, Pavel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Language :

English

Title :

Another Generalization of Abelian Equivalence: Binomial Complexity of Infinite Words

Publication date :

2013

Event name :

WORDS 2013

Event place :

Turku, Finland

Event date :

from 16-09-2013 to 20-09-2013

Audience :

International

Journal title :

Lecture Notes in Computer Science

ISSN :

0302-9743

eISSN :

1611-3349

Publisher :

Springer, Berlin, Germany

Special issue title :

Combinatorics on Words

Volume :

8079

Pages :

217-228

Peer reviewed :

Peer reviewed

Commentary :

This is the long version corresponding to the submission (limited to 12 pages). It contains an appendix with the omitted proofs.

Available on ORBi :

since 27 May 2013

Statistics

Number of views

205 (30 by ULiège)

Number of downloads

342 (7 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

Avgustinovich, S.V., Fon-Der-Flaass, D.G., Frid, A.E.: Arithmetical complexity of infinite words. In: Ito, M., Imaoka, T. (eds.) Words, Languages &Combinatorics III, pp. 51-62. World Scientific Publishing (2003)
Brlek, S.: Enumeration of factors in the Thue-Morse word. Discrete Appl. Math. 24, 83-96 (1989)
Berstel, J., Crochemore, M., Pin, J.-E.: Thue-Morse sequence and p-adic topology for the free monoid. Disc. Math. 76, 89-94 (1989)
Currie, J.: Personal communication (June 3, 2013)
de Luca, A., Varricchio, S.: On the factors of the Thue-Morse word on three symbols. Inform. Process. Lett. 27, 281-285 (1988)
Erdos, P.: Some unsolved problems. Magyar Tud. Akad. Mat. Kutato Int. Kozl. 6, 221-254 (1961)
Kamae, T., Zamboni, L.: Sequence entropy and the maximal pattern complexity of infinite words. Ergodic Theory Dynam. Systems 22, 1191-1199 (2002)
Karhumaki, J., Saarela, A., Zamboni, L.Q.: On a generalization of Abelian equivalence and complexity of infinite words, arXiv:1301.5104
Huova, M., Karhumaki, J.: Observations and problems on k-abelian avoidability. In: Combinatorial and Algorithmic Aspects of Sequence Processing (Dagstuhl Seminar 11081), pp. 2215-2219 (2011)
Keranen, V.: Abelian squares are avoidable on 4 letters. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol. 623, pp. 41-52. Springer, Heidelberg (1992)
Leech, J.: A problem on strings of beads. Math. Gazette 41, 277-278 (1957)
Lothaire, M.: Combinatorics on Words. Cambridge Mathematical Library. Cambridge University Press (1997)
Lothaire, M.: Algebraic Combinatorics on Words. Encyclopedia of Mathematics and its Applications, vol. 90 Cambridge University Press (2002)
Pytheas Fogg, N., Berthe, V., Ferenczi, S., Mauduit, C., Siegel, A. (eds.): Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics, vol. 1794. Springer, Berlin (2002)
Rigo, M., Salimov, P.: Another Generalization of Abelian Equivalence: Binomial Complexity of Infinite Words (long version) (preprint, 2013), http://hdl.handle.net/2268/149313