On generalized Lyndon words. (English) Zbl 1426.68229
A generalized lexicographical order is defined so that the order between two words depends on the length of their common prefix and is defined by the chosen total order between letters in a given position. For example, in the alternating lexicographic order, \(a<b\) at odd positions and \(b<a\) at even positions. Generalized Lyndon words are defined with respect to a given generalized lexicographic order as follows: a finite word \(w\) is a generalized Lyndon word if for every factorisation \(w=uv\) we have \(w^{\omega}<(vu)^{\omega}\). Such words were defined in 2005 by the third author of the paper (see [C. Reutenauer, Sémin. Lothar. Comb. 54, B54h, 16 p. (2005; Zbl 1183.68445)]).
This paper contains shorter proofs of the results of the previous paper, some new characterisations of generalized Lyndon words and particular results on classical Lyndon words and on the alternating order.
This paper contains shorter proofs of the results of the previous paper, some new characterisations of generalized Lyndon words and particular results on classical Lyndon words and on the alternating order.
Reviewer: Anna Frid (Marseille)
MSC:
| 68R15 | Combinatorics on words |
Keywords:
generalized Lyndon words; nonincreasing Lyndon factorization; alternating lexicographical order; Lyndon wordsCitations:
Zbl 1183.68445References:
| [1] | Apostolico, Alberto; Crochemore, Maxime, Fast parallel Lyndon factorization with applications, Math. Syst. Theory, 28, 2, 89-108 (1995) · Zbl 0815.68066 |
| [2] | Beauquier, Danièle; Nivat, Maurice, On translating one polyomino to tile the plane, Discrete Comput. Geom., 6, 6, 575-592 (1991) · Zbl 0754.05030 |
| [3] | Bergman, George M., Centralizers in free associative algebras, Trans. Amer. Math. Soc., 137, 327-344 (1969) · Zbl 0175.31501 |
| [4] | Boasson, Luc; Carton, Olivier, Transfinite Lyndon words, (Developments in Language Theory. Developments in Language Theory, Lecture Notes in Comput. Sci., vol. 9168 (2015), Springer: Springer Cham), 179-190 · Zbl 1434.68378 |
| [5] | Bonizzoni, Paola; De Felice, Clelia; Zaccagnino, Rocco; Zizza, Rosalba, Inverse Lyndon words and inverse Lyndon factorizations of words, Adv. in Appl. Math., 101, 281-319 (2018) · Zbl 1402.68143 |
| [6] | Bonomo, Silvia; Mantaci, Sabrina; Restivo, Antonio; Rosone, Giovanna; Sciortino, Marinella, Sorting conjugates and suffixes of words in a multiset, Internat. J. Found. Comput. Sci., 25, 8, 1161-1175 (2014) · Zbl 1310.68172 |
| [7] | Brlek, Srečko; Lachaud, Jacques-Olivier; Provençal, Xavier; Reutenauer, Christophe, Lyndon + Christoffel = digitally convex, Pattern Recognit., 42, 10, 2239-2246 (2009) · Zbl 1176.68175 |
| [8] | Charlier, Émilie; Philibert, Manon; Stipulanti, Manon, Nyldon Words (2018), URL: · Zbl 1419.68066 |
| [9] | Choffrut, Christian; Karhumäki, Juhani, Combinatorics of Words, Handbook of Formal Languages, vol. 1, 329-438 (1997), Springer: Springer Berlin |
| [10] | Crochemore, Maxime; Russo, Luís M. S., Cartesian trees and Lyndon trees (2017), CoRR · Zbl 1436.68274 |
| [11] | Duval, Jean-Pierre, Factorizing words over an ordered alphabet, J. Algorithms, 4, 4, 363-381 (1983) · Zbl 0532.68061 |
| [12] | Grinberg, Darij, “Nyldon words”: understanding a class of words factorizing the free monoid increasingly (2014), URL |
| [13] | Lothaire, M., Combinatorics on Words, Cambridge Mathematical Library (1997), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0874.20040 |
| [14] | Lothaire, M., Algebraic Combinatorics on Words, Encyclopedia of Mathematics and Its Applications, vol. 90 (2002), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1001.68093 |
| [15] | Lothaire, M., Applied Combinatorics on Words, Encyclopedia of Mathematics and Its Applications, vol. 105 (2005), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1133.68067 |
| [16] | Lyndon, Roger C., On Burnside’s problem, Trans. Amer. Math. Soc., 77, 202-215 (1954) · Zbl 0058.01702 |
| [17] | Perrin, Dominique; Restivo, Antonio, Words, (Handbook of Enumerative Combinatorics. Handbook of Enumerative Combinatorics, Discrete Math. Appl. (Boca Raton) (2015), CRC Press: CRC Press Boca Raton, FL), 485-539 · Zbl 1386.68122 |
| [18] | Reutenauer, Christophe, Free Lie Algebras, London Mathematical Society Monographs. New Series, vol. 7 (1993), The Clarendon Press, Oxford University Press: The Clarendon Press, Oxford University Press New York · Zbl 0798.17001 |
| [19] | Reutenauer, Christophe, Mots de Lyndon généralisés, Sém. Lothar. Combin. B, 54h, 16, Article 54 pp. (2005) · Zbl 1183.68445 |
| [20] | Siromoney, Rani; Mathew, Lisa; Dare, V. R.; Subramanian, K. G., Infinite Lyndon words, Inform. Process. Lett., 50, 2, 101-104 (1994) · Zbl 0803.68093 |
| [21] | Ufnarovskij, V. A., Combinatorial and asymptotic methods in algebra, (Algebra, VI. Algebra, VI, Encyclopaedia Math. Sci., vol. 57 (1995), Springer: Springer Berlin), 1-196, [MR1060321 (92h:16024)] · Zbl 0826.16001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
