Nyldon words

Charlier, Emilie; Philibert, Manon; Stipulanti, Manon

doi:10.1016/j.jcta.2019.04.002

Download

Article (Scientific journals)

Nyldon words

Charlier, Emilie; Philibert, Manon; Stipulanti, Manon

2019 • In Journal of Combinatorial Theory. Series A, 167, p. 60-90

Peer Reviewed verified by ORBi

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

DOI
10.1016/j.jcta.2019.04.002

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

Nyldon-final.pdf

Author preprint (356.51 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

Lyndon words; Factorization of the free monoid; Code; Standard factorization; Lazard sets; Hall sets

Abstract :

[en] The Chen-Fox-Lyndon theorem states that every finite word over a fixed alphabet can be uniquely factorized as a lexicographically nonincreasing sequence of Lyndon words. This theorem can be used to define the family of Lyndon words in a recursive way. If the lexicographic order is reversed in this definition, we obtain a new family of words, which are called the Nyldon words. In this paper, we show that every finite word can be uniquely factorized into a lexicographically nondecreasing sequence of Nyldon words. Otherwise stated, Nyldon words form a complete factorization of the free monoid with respect to the decreasing lexicographic order. Then we investigate this new family of words. In particular, we show that Nyldon words form a right Lazard set.

Disciplines :

Mathematics

Author, co-author :

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

Philibert, Manon

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

Language :

English

Title :

Nyldon words

Publication date :

2019

Journal title :

Journal of Combinatorial Theory. Series A

ISSN :

0097-3165

Publisher :

Elsevier, Atlanta, Georgia

Volume :

167

Pages :

60-90

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 30 January 2019

Statistics

Number of views

60 (17 by ULiège)

Number of downloads

64 (9 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

Bokut, L.A., Chen, Y., Li, Y., Lyndon-Shirshov basis and anti-commutative algebras. J. Algebra 378 (2013), 173–183.
Bonizzoni, P., De Felice, C., Zaccagnino, R., Zizza, R., Inverse Lyndon words and inverse Lyndon factorizations of words. Adv. in Appl. Math. 101 (2018), 281–319.
Berstel, J., Perrin, D., The origins of combinatorics on words. European J. Combin. 28:3 (2007), 996–1022.
Berstel, J., Perrin, D., Reutenauer, C., Codes and Automata. Encyclopedia of Mathematics and its Applications., vol. 129, 2010, Cambridge University Press, Cambridge.
Chen, K.-T., Fox, R.H., Lyndon, R.C., Free differential calculus. IV. The quotient groups of the lower central series. Ann. of Math. (2) 68 (1958), 81–95.
Duval, J.-P., Factorizing words over an ordered alphabet. J. Algorithms 4:4 (1983), 363–381.
Grinberg, D., “Nyldon words”: understanding a class of words factorizing the free monoid increasingly. https://mathoverflow.net/questions/187451/, 2014.
Knuth, D.E., The Art of Computer Programming, vol. 4A. Combinatorial Algorithms. Part 1. 2011, Addison-Wesley, Upper Saddle River, NJ.
Lothaire, M., Combinatorics on Words. Cambridge Mathematical Library, 1997, Cambridge University Press, Cambridge.
Mélançon, G., Combinatorics of Hall trees and Hall words. J. Combin. Theory Ser. A 59:2 (1992), 285–308.
Perrin, D., Reutenauer, C., Hall sets, Lazard sets and comma-free codes. Discrete Math. 341:1 (2018), 232–243.
Reutenauer, C., Free Lie Algebras. London Mathematical Society Monographs. New Series, vol. 7, 1993, The Clarendon Press, Oxford University Press, Oxford Science Publications, New York.
Schützenberger, M.-P., On a factorisation of free monoids. Proc. Amer. Math. Soc. 16 (1965), 21–24.
Širšov, A.I., On free Lie rings. Mat. Sb. N.S. 45:87 (1958), 113–122.
Širšov, A.I., On the bases of a free Lie algebra. Algebra i Logika Sem. 1:1 (1962), 14–19.
Viennot, G., Algèbres de Lie libres et monoïdes libres. Bases des algèbres de Lie libres et factorisations des monoïdes libres Lecture Notes in Mathematics, vol. 691, 1978, Springer, Berlin.