Binary Bubble Languages and Cool-lex Order

Frank Ruskey, Department of Computer Science, University of Victoria, British Columbia, Canada.
Joe Sawada, Department of Computer Science, University of Guelph, Ontario, Canada.
Aaron Williams, Department of Computer Science, Carleton University, Ontario, Canada.

Abstract:

A bubble language is a set of binary strings with a simple closure property: The leftmost 01 of any string can be replaced by 10 to obtain another string in the set. Natural representations of many combinatorial objects are bubble languages. Examples include binary string representations of k-ary trees, unit interval graphs, linear extensions of B-posets, binary necklaces and Lyndon words, and feasible solutions to knapsack problems. In co-lexicographic order, fixed-density binary strings are ordered so that their suffixes of the form 10i occur (recursively) in the order i = max, max-1, ..., min+1, min for some values of max and min. In cool-lex order the suffixes occur (recursively) in the order max-1, ..., min+1, min, max. This small change has significant consequences. We prove that the strings in any bubble language appear in a Gray code order when listed in cool-lex order. This Gray code may be viewed from two different perspectives. On the one hand, successive binary strings differ by one or two transpositions, and on the other hand, they differ by a shift of some substring on position to the right. This article also provides the theoretical foundation for many efficient generation algorithms, as well as the first construction of fixed-density de Bruijn sequences; results that will appear in subsequent papers.

Selected Publications that refer to this paper:
Back to list of publications.