%0 Journal Article %1 citeulike:73598 %A Sawada, J. %A Ruskey, F. %D 2003 %J Journal of Algorithms %K algorithm fast generate necklaces %N 1 %P 21--26 %R 10.1016/S0196-6774(02)00286-9 %T Generating Lyndon brackets.: An addendum to: Fast algorithms to generate necklaces, unlabeled necklaces and irreducible polynomials over GF(2) %U http://dx.doi.org/10.1016/S0196-6774(02)00286-9 %V 46 %X It is well known that the Lyndon words of length n can be used to construct a basis for the nth 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 nth 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(n2).

@article{citeulike:73598, abstract = {It is well known that the Lyndon words of length n can be used to construct a basis for the nth 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 nth 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(n2).}, added-at = {2007-08-18T13:22:24.000+0200}, author = {Sawada, J. and Ruskey, F.}, biburl = {https://www.bibsonomy.org/bibtex/227331be3ce57d26270f146d7568a824c/a_olympia}, citeulike-article-id = {73598}, description = {citeulike}, doi = {10.1016/S0196-6774(02)00286-9}, interhash = {413d30971404ac59c49d4d9003d17050}, intrahash = {27331be3ce57d26270f146d7568a824c}, journal = {Journal of Algorithms}, keywords = {algorithm fast generate necklaces}, month = {January}, number = 1, pages = {21--26}, timestamp = {2007-08-18T13:22:55.000+0200}, title = {Generating Lyndon brackets.: An addendum to: Fast algorithms to generate necklaces, unlabeled necklaces and irreducible polynomials over GF(2)}, url = {http://dx.doi.org/10.1016/S0196-6774(02)00286-9}, volume = 46, year = 2003 }