6533b825fe1ef96bd128317c

RESEARCH PRODUCT

More restrictive Gray codes for necklaces and Lyndon words

Vincent Vajnovszki

subject

Open problemBase (topology)Computer Science ApplicationsTheoretical Computer ScienceCombinatoricsSet (abstract data type)Gray codeCombinatorics on wordsAlgorithmicsSignal ProcessingCode (cryptography)Binary codeInformation SystemsMathematics

description

In the last years, the order induced by the Binary Reflected Gray Code or its generalizations shown an increasing interest. In this note we show that the BRGC order induces a cyclic 2-Gray code on the set of binary necklaces and Lyndon words and a cyclic 3-Gray code on the unordered counterparts. This is an improvement and a generalization to unlabeled words of the result in [V. Vajnovszki, Gray code order for Lyndon words, Discrete Math. Theoret. Comput. Sci. 9 (2) (2007) 145-152; M. Weston, V. Vajnovszki, Gray codes for necklaces and Lyndon words of arbitrary base, Pure Mathematics and Applications/Algebra and Theoretical Computer Science, in press]; however an algorithmic implementation of our Gray codes remains an open problem.

yearjournalcountryeditionlanguage
2008-04-01Information Processing Letters
https://doi.org/10.1016/j.ipl.2007.10.011