15 citations · 47 across the 15 of their papers we have counts for
Showing cs.DMShow all
3 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
Finding the growth rate of a regular language in polynomial time
Dalia Krieger, Narad Rampersad, Jeffrey Shallit
We give an O(n^3+n^2 t) time algorithm to determine whether an NFA with n states and t transitions accepts a language of polynomial or exponential growth. We also show that given a…
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…