3 papers
cs.CC2008
On NFAs Where All States are Final, Initial, or Both
Jui-Yi Kao, Narad Rampersad, Jeffrey Shallit
We examine questions involving nondeterministic finite automata where all states are final, initial, or both initial and final. First, we prove hardness results for the nonuniversa…
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…
math.CO2006
Words avoiding repetitions in arithmetic progressions
Jui-Yi Kao, Narad Rampersad, Jeffrey Shallit +1
Carpi constructed an infinite word over a 4-letter alphabet that avoids squares in all subsequences indexed by arithmetic progressions of odd difference. We show a connection betwe…