Axiomatizing rational power series over natural numbers

摘要

Iteration semirings are Conway semirings satisfying Conway's group identities. We show that the semirings N~(rat)«Σ~*» of rational power series with coefficients in the semiring N of natural numbers are the free partial iteration semirings. Moreover, we characterize the semirings N_∞~(rat)«Σ~*» as the free semirings in the variety of iteration semirings defined by three additional simple identities, where N_∞ is the completion of N obtained by adding a point at 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 semirings N_∞~(rat)«Σ~*», equipped with the sum order, are free in the class of symmetric inductive *-semirings. This characterization corresponds to Kozen's axiomatization of regular languages.