Axiomatizing rational power series over natural numbers

Iteration semi-rings are Conway semi-rings satisfying Conway’s group identities. We show that the semi-rings N rat 《 Σ ∗ 》 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 《 Σ...

Full description

Saved in:
Bibliographic Details
Published in:Information and computation 2009-07, Vol.207 (7), p.793-811
Main Authors: Bloom, S.L., Ésik, Z.
Format: Article
Language:English
Subjects:
Applied sciences
Computer science
control theory
systems
Exact sciences and technology
Miscellaneous
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Iteration semi-rings are Conway semi-rings satisfying Conway’s group identities. We show that the semi-rings N rat 《 Σ ∗ 》 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 N ∞ rat 《 Σ ∗ 》 , 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.
ISSN:0890-5401
1090-2651
DOI:10.1016/j.ic.2009.02.003