Generating Lyndon Brackets

Abstract:

It is well known that the Lyndon words of length n can be used to construct a basis for the n-th homogeneous component of the free Lie algebra. We develop an algorithm that uses a dynamic programming table to efficiently generate the standard bracketing for all Lyndon words of length n, thus constructing a basis for the n-th homogeneous component of the free Lie algebra. The algorithm runs in linear amortized time; i.e., O(n) time per basis element. For a single Lyndon word, the table (and thus the standard bracketing) can be computed in time O(n²).

Frank Ruskey, Department of Computer Science, University of Victoria, Canada.
Joe Sawada, Department of Computer Science, University of Victoria, Canada.

• The postscript file is 233,673 bytes, the dvi file is 21760 bytes, the pdf file is 128738 bytes.
• Journal of Algorithms, 46 (2003) 21-26.
• Preliminary version appears as the KAM-DIMATIA technical report number 2001-519 ( http://nikam.ms.mff.cuni.cz/~kamserie/).

• Christopher Degni and Arthur A. Drisko, Gray-ordered Binary Necklaces, Electronic Journal of Combinatorics, Paper R7 (Jan 3, 2007) 23 pages.
• Frédérique Bassino, Julien Clément, and Cyril Nicaud, The Standard Factorization of Lyndon Words: an Average Point of View, Discrete Mathematics, 290 (2005) pp. 1–25.
• Frédérique Bassino, Julien Clément, and Cyril Nicaud, Lyndon words with a fixed standard right factor. In, J. Ian Munro, editors, 15th ACM-SIAM Annual Symposium on Discrete Algorithms (SODA 2004). New Orleans, Louisiana, USA. January 2004. pp. 646–647.