Gray Code Order for Lyndon Words
Vincent Vajnovszki
Abstract
At the 4th Conference on Combinatorics on Words,
Christophe Reutenauer posed the question of whether the dual reflected order
yields a Gray code on the Lyndon family.
In this paper we give a positive answer.
More precisely, we present an O(1)-average-time algorithm for generating length n
binary pre-necklaces, necklaces and Lyndon words in Gray code order.
Full Text: PostScript PDF