2007/12/09 by Stephen L. Bloom, S. L. Bloom, Bloom, S. L. +3
Computer Science · #Advanced Algebra and Logic #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #cs.DM #cs.LO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0712.1337
openalex publication_date 2007/12/09 · arxiv created 2008/12/09 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \N of natural numbers are the free partial iteration semirings. Moreover, we characterize the semirings \N_∞\rat\llangle Σ^* \rrangle 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 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_∞\rat\llangle Σ^* \rrangle, equipped with the sum order, are free in the class of symmetric inductive ^*-semirings. This characterization corresponds to Kozen's axiomatization of regular languages.