It is well known that the set of all natural numbers divisible by a fixed modulus can be recognized by a finite state machine, assuming that the numbers are written in standard base- representation. It is much harder to determine the state complexity of the minimal recognizer [1]. In this article we discuss the size … Continue reading Divisibility and State Complexity