## The Frobenius Problem in a Free Monoid

#### Jui-Yi Kao, Jeffrey Shallit, Zhi Xu

The classical Frobenius problem is to compute the largest number g not
representable as a non-negative integer linear combination of non-negative
integers x_1, x_2, ..., x_k, where gcd(x_1, x_2, ..., x_k) = 1. In this paper
we consider generalizations of the Frobenius problem to the noncommutative
setting of a free monoid. Unlike the commutative case, where the bound on g is
quadratic, we are able to show exponential or subexponential behavior for an
analogue of g, depending on the particular measure chosen.

[paper|preprint|proceedings]

[home]