An abelian processor is an automaton whose output is independent of the order of its inputs. Bond and Levine have proved that a network of abelian processors performs the same computation regardless of processing order (subject only to a halting condition). We prove that any finite abelian processor can be emulated by a network of certain very simple abelian processors, which we call gates. The most fundamental gate is a toppler, which absorbs input particles until their number exceeds some given threshold, at which point it topples, emitting one particle and returning to its initial state. With the exception of an adder gate, which simply combines two streams of particles, each of our gates has only one input wire, which sends letters (‘particles’) from a unary alphabet. Our results can be reformulated in terms of the functions computed by processors, and one consequence is that any increasing function from ℕk to ℕℓ that is the sum of a linear function and a periodic function can be expressed in terms of (possibly nested) sums of floors of quotients by integers.

We study the coefficients of algebraic functions ∑n≥0fnzn. First, we recall the too-little-known fact that these coefficients fn always admit a closed form. Then we study their asymptotics, known to be of the type fn ~ CAnnα. When the function is a power series associated to a context-free grammar, we solve a folklore conjecture: the critical exponents α cannot be 1/3 or −5/2; they in fact belong to a proper subset of the dyadic numbers. We initiate the study of the set of possible values for A. We extend what Philippe Flajolet called the Drmota–Lalley–Woods theorem (which states that α=−3/2 when the dependency graph associated to the algebraic system defining the function is strongly connected). We fully characterize the possible singular behaviours in the non-strongly connected case. As a corollary, the generating functions of certain lattice paths and planar maps are not determined by a context-free grammar (i.e., their generating functions are not ℕ-algebraic). We give examples of Gaussian limit laws (beyond the case of the Drmota–Lalley–Woods theorem), and examples of non-Gaussian limit laws. We then extend our work to systems involving non-polynomial entire functions (non-strongly connected systems, fixed points of entire functions with positive coefficients). We give several closure properties for ℕ-algebraic functions. We end by discussing a few extensions of our results (infinite systems of equations, algorithmic aspects).