### Strings

Combinatorics is the study of arrangements,
and so it is perhaps not surprising that there are literally
thousands of combinatorial problems that arise in Computer Science.
I have been fascinated by combinatorial problems since the 1960s,
when I realized that the solution of the equations I was using to
analyze the concrete sections of the Toronto subway
depended critically on how the rows and columns of the matrix
were *arranged*.
I didn't know it at the time, but this was the graph bandwidth
problem, since shown to be a very difficult one (NP-complete).
Over the last ten years my research has focussed more and more on
combinatorial objects called "strings" --
that is, sequences of letters such as *abaababa*
or *ablewasiereisawelba* drawn from a specified alphabet.
I am interested in algorithms that compute patterns in strings,
especially repetitive patterns. Patterns of this kind are of interest
in a great many diverse fields: DNA sequence analysis,
cryptography, analysis of musical texts, data compression,
and computational geometry.
When a colleague originally suggested that I start to work in the
field of "stringology", my initial response was that strings were
too easy, they had no structure, there could be no interesting
problems and only trivial applications -- how wrong I was!

If you think you might be interested in this area of research,
you can download some of the papers listed under
Refereed Publications
and take a look at them.
My work is very mathematical in nature, but it is mostly
discrete mathematics and does not usually require
a lot of specialized knowledge --
just a good CPU!

*
Last revised:
Monday, 11-Feb-2002 11:01:55 EST
*
** Hits = [an error occurred while processing this directive] **