The Frobenius Problem in a Free Monoid

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

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.
19 pages; preliminary announcement

Keywords

Discrete Mathematics, Combinatorics, F.4.3

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/136600

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0708.3224
 http://arxiv.org/abs/0708.3224

Collections

arXiv