[seqfan] Re: Message to Sequence Fans - what are your fields of expertise?

[Dale Gerdemann]

Dear Neil,

I'll reply publicly to your appeal in the hope that it might entice
somebody (including maybe myself) into submitting some new sequences.

I have worked quite a bit with suffix arrays/suffix trees. This is a data
structure commonly used in bioinformatics and sometimes in computational
linguistics. There are lots of combinatorial questions related to this data
structure, some of which are discussed in the book: Suffix Arrays in Theory
and Practice: Combinatorics of and Algorithms on the Suffix Array Data
Structure Paperback by Klaus-Bernd Schürmann.

An example question (not answered by Schürmann) is: How many longest common
prefix arrays are possible for the set of texts of length n over an
alphabet of size m. For example, "banana" is a text over the alphabet
{a,b,n}. The ordered suffixes are: "a", "ana", "anana", "banana",
"na","nana". The common prefix of "a" and "ana" is of length 1; for "ana"
and "anana" the common prefix is of length 3, etc. Collecting all these
lengths, you get the so-called lcp array: [1,3,0,0,2]. So [1,3,0,0,2] is a
possible lcp array for n=6 and m=3. On the other hand, it's easy to see
that [0,0,0,0,0] would not be a possible lcp array for these values of n
and m. But it's not obvious to me how you would count the full set of
possible lcp arrays.

As far as I know, the OEIS contains almost no sequences specific to suffix
arrays (one exception being A098830). Clearly a gap to be filled.

Dale Gerdemann



On Tue, Jan 21, 2014 at 11:47 PM, Neil Sloane <njasloane at gmail.com> wrote:

> We often get sequences submitted to the OEIS in areas
> where we are not experts. If you are an expert in some branch
> of science (representation theory, particle physics, combinatorial
> chemistry, ...) and would be willing to help, please send me an email.
> I will collect the information and give it to the Editors in Chief.
>
> Neil Sloane (njasloane at gmail.com)
>
>
> --
> Dear Friends, I have now retired from AT&T. New coordinates:
>
> Neil J. A. Sloane, President, OEIS Foundation
> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
> Phone: 732 828 6098; home page: http://NeilSloane.com
> Email: njasloane at gmail.com
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>