Binary Bubble Languages and Coollex 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 kary trees,
unit interval graphs, linear extensions of Bposets, binary
necklaces and Lyndon words, and feasible solutions to knapsack problems.
In colexicographic order, fixeddensity binary strings are ordered so that
their suffixes of the form 10^{i} occur (recursively) in the
order i = max, max1, ..., min+1, min for some values of max and
min.
In coollex order the suffixes occur (recursively) in the order
max1, ..., 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 coollex 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 fixeddensity de Bruijn sequences;
results that will appear in subsequent papers.

To appear in Journal of Combinatorial Theory, Series A.

Submitted September 15, 2010.

Accepted May 17, 2011.

The postscript file.

The pdf file.
Selected Publications that refer to this paper:

Someday there will be some!
Back to list of publications.