LIPIcs.STACS.2008.1362.pdf
- Filesize: 188 kB
- 12 pages
Document
The Frobenius Problem in a Free Monoid
Authors
-
Part of:
Volume:
25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2008-02-06
Cite AsGet BibTex
Jui-Yi Kao, Jeffrey Shallit, and Zhi Xu. The Frobenius Problem in a Free Monoid. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 421-432, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.STACS.2008.1362
https://doi.org/10.4230/LIPIcs.STACS.2008.1362
Abstract
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.
Keywords
- Combinatorics on words
- Frobenius problem
- free monoid
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads