Computer Science – Logic in Computer Science
Scientific paper
2007-12-09
Computer Science
Logic in Computer Science
Scientific paper
Iteration semirings are Conway semirings satisfying Conway's group identities. We show that the semirings $\N^{\rat}\llangle \Sigma^* \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 \Sigma^* \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 \Sigma^* \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.
Bloom Stephen L.
Esik Zoltan
No associations
LandOfFree
Axiomatizing rational power series does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Axiomatizing rational power series, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Axiomatizing rational power series will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-241953