[seqfan] Re: What is the name for a string that contains every k-digit base-b substring?

[Jim Nastos]

It's true: as you say, every cyclic sequence can be turned into a
"regular" or  "linear" sequence by copying a few bits from the start
and tacking them onto the end.

But I don't think it works the only way: there may be some linear
sequences with this desired property where the first few bits don't
match the last few bits and so can't be turned into a cycle. I'm
actually not sure if this ever does happen with these normal de Bruijn
sequences (and it might not, since it might be that the
eulerian/hamiltonian paths on de Bruijn graphs guarantee that
sequences have to end where they start, or something...)
... but I encountered this when I looked at these type of sequences
with added restrictions. I called a "square-free de Bruijn sequence" a
sequence of the type you mention without any adjacent repeated
substring (or any length). So even with an alphabet of {a,b,c,d} and
wanting to have all 5-length strings in it, this square-free
restriction would restrict any occurrence of 'aa' or 'bb' or 'abab' or
'abcabc' and so on. This obviously loses a lot of the 5-length
substrings and thus loses its characterization with de Bruijn graphs,
but it turned out that these type of sequences still exist in fairly
large numbers for various combinations of n and k, and not exist at
all for other combinations.
  The frustrating thing with these restricted de Bruijn sequences is
that for some n,k pairs, no cyclic sequences existed but linear ones
did exist (if I recall correctly.... I didn't publish this stuff at
all, but I think I submitted an OEIS sequnce or two on these.)
  Best,
JN


On Mon, Mar 19, 2012 at 11:15 AM, Marc LeBrun <mlb at well.com> wrote:
>>="Jim Nastos" <nastos at gmail.com>
>> Aren't these the de Bruijn sequences?
>
> Yes, thanks!
>
> (technically these are circular, but you can of course snip them and add a
> little tail...)
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/