文章基本信息

标题：The Frobenius Problem in a Free Monoid
本地全文：下载
作者：Jui-Yi Kao ; Jeffrey Shallit ; Zhi Xu 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2008
卷号：1
页码：421-432
DOI：10.4230/LIPIcs.STACS.2008.1362
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Combinatorics on words; Frobenius problem; free monoid