کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
426669 | 686149 | 2009 | 19 صفحه PDF | دانلود رایگان |
Iteration semi-rings are Conway semi-rings satisfying Conway’s group identities. We show that the semi-rings Nrat《Σ∗》 of rational power series with coefficients in the semi-ring N of natural numbers are the free partial iteration semi-rings. Moreover, we characterize the semi-rings N∞rat《Σ∗》 as the free semi-rings in the variety of iteration semi-rings 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 semi-rings , equipped with the sum order, are free in the class of symmetric inductive ∗-semi-rings. This characterization corresponds to Kozen’s axiomatization of regular languages.
Journal: Information and Computation - Volume 207, Issue 7, July 2009, Pages 793-811