June 20, 2013
Jeffrey Shallit, David Cheriton School of Computer Science, Faculty of Math, University of Waterloo.
Portrait by Chris Hughes
The classical but oddly little-known Frobenius problem from number theory is the following: given a set of positive integers with greatest common divisor equal to 1, find the largest integer not representable as a non-negative integer linear combination of the set elements. This largest integer is called the Frobenius number. For example, the Frobenius number of 6, 9, and 20 is 43. In this talk I will survey some of the known results on this problem and its applications to computer science, and a new generalization of this problem to words (strings of symbols).
Jeffrey Shallit (University of Waterloo, Canada)
