Search

Iteration semi-rings are Conway semi-rings satisfying Conway's group identities. We show that the semi-rings N^r^a^t > 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"~"^"r"^"a"^"t > 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 N"~^r^a^t >, 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.