9 citations · 16 across the 4 of their papers we have counts for
Showing cs.DMShow all
2 papers · 1 filter
cs.DM2008★ 4 cited
An NP-hardness Result on the Monoid Frobenius Problem
Zhi Xu, J. Shallit
The following problem is NP-hard: given a regular expression , decide if is not co-finite.
cs.DM2007
The Frobenius Problem in a Free Monoid
Jui-Yi Kao, Jeffrey Shallit, Zhi Xu
The classical Frobenius problem is to compute the largest number g not representable as a non-negative integer linear combination of non-negative integers x_1, x_2, ..., x_k, where…