2026-07-25T01:58:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1362 2024-03-06T10:33:00Z ddc:004 open_access

The Frobenius Problem in a Free Monoid Kao, Jui-Yi Shallit, Jeffrey Xu, Zhi Combinatorics on words Frobenius problem free monoid 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, ldots, x_k$, where $gcd(x_1, x_2, ldots, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jui-Yi Kao and Jeffrey Shallit and Zhi Xu 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1362 urn:nbn:de:0030-drops-13620 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1362 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode