# zbMATH — the first resource for mathematics

The Frobenius problem in a free monoid. (English) Zbl 1259.68166
Albers, Susanne (ed.) et al., STACS 2008. 25th international symposium on theoretical aspects of computer science, Bordeaux, France, February 21–23, 2008. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-06-4). LIPIcs – Leibniz International Proceedings in Informatics 1, 421-432, electronic only (2008).
Summary: The classical Frobenius problem over $${\mathbb N}$$ is to compute the largest integer $$g$$ not representable as a non-negative integer linear combination of non-negative integers $$x_1, x_2,\dots, x_k$$, where $$\gcd(x_1, x_2,\dots, x_k) = 1$$. In this paper we consider novel 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 several analogues of $$g$$, with the precise bound depending on the particular measure chosen.
For the entire collection see [Zbl 1213.68020].

##### MSC:
 68R15 Combinatorics on words
##### Keywords:
combinatorics on words; Frobenius problem; free monoid
Full Text: