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].

68R15 Combinatorics on words
Full Text: DOI Link arXiv