Stably computable predicates are semilinear.

Dana Angluin, James Aspnes, David Eisenstat

Browse the full PODC paper archive.