Journal
THEORETICAL COMPUTER SCIENCE
Volume 502, Issue -, Pages 46-54Publisher
ELSEVIER
DOI: 10.1016/j.tcs.2012.01.013
Keywords
Lyndon word; Necklace; Pseudo-necklace; Gray code; Cool-lex; Fixed-density; de Bruijn sequence
Categories
Funding
- NSERC
Ask authors/readers for more resources
This paper develops a constant amortized time algorithm to produce a cyclic cool-lex Gray code for fixed-density binary necklaces, Lyndon words, and pseudo-necklaces. It is the first Gray code for these objects that achieves this time bound. The algorithm is applied: (i) to develop a constant amortized time cyclic Gray code for necklaces, Lyndon words, and pseudo-necklaces ordered by density and (ii) to obtain a fixed-density de Bruijn sequence using constant time per n bits on average. In addition to Gray code order, the algorithms can be easily modified to output the strings in co-lex order. (C) 2012 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available