Axiomatizing rational power series over natural numbers

Iteration semi-rings are Conway semi-rings satisfying Conway’s group identities. We show that the semi-rings Nrat《Σ∗》 of rational power series with coefficients in the semi-ring N of natural numbers are the free partial iteration semi-rings. Moreover, we characterize the semi-rings N∞rat《Σ∗》 as the free semi-rings in the variety of iteration semi-rings defined by three additional simple identities, where N∞ is the completion of N obtained by adding a point of infinity. We also show that this latter variety coincides with the variety generated by the complete, or continuous semirings. As a consequence of these results, we obtain that the semi-rings , equipped with the sum order, are free in the class of symmetric inductive ∗-semi-rings. This characterization corresponds to Kozen’s axiomatization of regular languages.