2 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…
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…