Generating Lyndon brackets. An addendum to: Fast algorithms to generate necklaces, unlabeled necklaces and irreducible polynomials over GF(2)

@misc{citeulike:71323, 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 ...}, author = {Sawada, J. and Ruskey, F. }, citeulike-article-id = {71323}, keywords = {brackets, irreducible, lyndon, necklaces, polynomials}, posted-at = {2004-12-30 12:44:49}, title = {Generating Lyndon brackets. An addendum to: Fast algorithms to generate necklaces, unlabeled necklaces and irreducible polynomials over GF(2)}, url = {http://citeseer.ist.psu.edu/sawada02generating.html} }

TY - GEN ID - citeulike:71323 L3 - citeulike-article-id:71323 TI - Generating Lyndon brackets. An addendum to: Fast algorithms to generate necklaces, unlabeled necklaces and irreducible polynomials over GF(2) N2 - 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 ... KW - brackets KW - irreducible KW - lyndon KW - necklaces KW - polynomials AU - Sawada, J AU - Ruskey, F UR - http://citeseer.ist.psu.edu/sawada02generating.html ER -