Unary finite automata vs. arithmetic progressions

Anthony Widjaja To

We point out a subtle error in the proof of Chrobak's theorem that every unary NFA can be represented as a union of arithmetic progressions that is at most quadratically large. We…