Axiomatizing rational power series

Simple item page
dc.creatorBloom, S. L.
dc.creatorEsik, Z.
dc.date2007-12-09
dc.date2008-12-09
dc.date.accessioned2026-07-07T12:09:54Z
dc.date.available2026-07-07T12:09:54Z
dc.descriptionIteration 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_\infty^{\rat}\llangle Σ^* \rrangle$ as the free semirings in the variety of iteration semirings defined by three additional simple identities, where $\N_\infty$ 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_\infty^{\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.
dc.identifierhttps://arxiv.org/abs/0712.1337
dc.identifierhttp://arxiv.org/abs/0712.1337
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/209788
dc.subjectLogic in Computer Science
dc.subjectDiscrete Mathematics
dc.titleAxiomatizing rational power series
dc.typetext

Files

Collections

arXiv