Counting with probabilistic and ultrametric finite automata

We investigate the state complexity of probabilistic and ultrametric finite automata for the problem of counting, i.e. recognizing the one-word unary language Cn = {1n}. We also review the known results for other types of automata. For one-way probabilistic automata, we construct a minimal 3-state automaton for counting to n with isolated cutpoint (but with decreasing isolation radius as n increases). We construct a two-way probabilistic automaton that counts to n with a constant number of states. We also show a minimal 2-state ultrametric automaton for counting.