automaton | k-automatic set

A k-automatic set is a set of integers whose base-k representations form a regular language, i.e., a language accepted by a finite automaton or state machine. If bases a and b are incompatible (do not have a common power) and if an a-automatic set S_a and b-automatic set S_b are both of density 0 over the integers, then it is believed that S_a intersection S_b is finite. However, this problem has not been settled. Some automatic sets, such as the 2-automatic consisting of numbers whose binary representations contain at most two 1s: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 16, 17, 18, ... (OEIS A048645) have a simple arithmetic expression. However, this is not the case for general k-automatic sets.