Axiomatizing rational power series

Abstract

Iteration semirings are Conway semirings satisfying Conway's group identities. We show that the semirings $\N^{\rat}\llangle Σ^* \rrangle$ of rational power series with coefficients in the semiring $\mathbb{N}$ of natural numbers are the free partial iteration semirings. Moreover, we characterize the semirings $\N_\infty^{\rat}\llangle Σ^* \rrangle$ as the free semirings in the variety of iteration semirings defined by three additional simple identities, where ${\mathbb{N}}_{\infty }$ is the completion of $\mathbb{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 semirings $\N_\infty^{\rat}\llangle Σ^* \rrangle$, equipped with the sum order, are free in the class of symmetric inductive ${}^{\ast }$-semirings. This characterization corresponds to Kozen's axiomatization of regular languages.