Home   Contact Research:   Events   Seminars People:   Faculty members   Graduate students   Postdoctoral fellows   Alumni   Postdoctoral positions Prospective Students:   Admission   Life at Waterloo   International Students

Algorithms and Complexity Seminar     Date: Friday, November 30, 2007 Time: 1:30 PM Place: DC1304         Title: The Frobenius Problem in a Free Monoid Speaker: Zhi Xu, School of Computer Science, University of Waterloo Abstract:   The classical Frobenius problem is to compute the largest integer $g$ not representable as non-negative integer linear combination of $x_1,x_2,\ldots,x_k$, where $x_1,x_2,\ldots,x_k$ are positive integers with $\gcd(x_1, x_2, \ldots, x_k)=1$. We generalize this problem to the non-commutative setting of a free monoid, where $S=\{u_1,u_2,\ldots,u_k\}$ is a set of words over a finite alphabet $\Sigma$ such that $S^*$, the set of all words factorizable into elements of $S$, is co-finite. We use techniques from automata theory and formal language theory to discuss the length of the longest word not in $S^*$. Unlike the commutative case, where the bound on $g(x_1,x_2,\ldots,x_k)$ is quadratic, we are able to prove that the length of the longest word not in $S^*$ is bounded above by $$\frac{2(2^n|\Sigma|^n-1)}{2|\Sigma|-1},$$ where $n=\max_{1\leq i\leq k}|u_i|$. Furthermore, we are able to show a tight (exponential) lower bound for the worst case of the form $$g(m,m|\Sigma|^{n-m}+n-m)$$ in the case where $S\subseteq\Sigma^m\cup\Sigma^n$, where $0 We obtain upper and lower bounds for other generalizations of the Frobenius problem, such as the state complexity of $S^*$, and we also obtain results on the total number of words not in $S^*$, generalizing an 1884 result of Sylvester.