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]