15 citations · 66 across the 26 of their papers we have counts for
Showing 2007 · cs.DMShow all
2 papers · 2 filters
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…