The Frobenius Problem in a Free Monoid
| dc.creator | Kao, Jui-Yi | |
| dc.creator | Shallit, Jeffrey | |
| dc.creator | Xu, Zhi | |
| dc.date | 2007-08-23 | |
| dc.date.accessioned | 2026-07-07T08:25:16Z | |
| dc.date.available | 2026-07-07T08:25:16Z | |
| dc.description | 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. | |
| dc.description | 19 pages; preliminary announcement | |
| dc.identifier | https://arxiv.org/abs/0708.3224 | |
| dc.identifier | http://arxiv.org/abs/0708.3224 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/136600 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Combinatorics | |
| dc.subject | F.4.3 | |
| dc.title | The Frobenius Problem in a Free Monoid | |
| dc.type | text |