2007/12/18 by S. L. Bloom, Bloom, S. L., Z. Esik +3
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.DM #cs.LO
paper · pdf · doi:10.48550/arxiv.0712.2952
arxiv created 2007/12/18 · arxiv updated 2015/03/13
A Conway semiring is a semiring S equipped with a unary operation ^*:S → S, always called 'star', satisfying the sum star and product star identities. It is known that these identities imply a Kleene type theorem. Some computationally important semirings, such as N or N\rat\llangle Σ^* \rrangle of rational power series of words on Σ with coefficients in N, cannot have a total star operation satisfying the Conway identities. We introduce here partial Conway semirings, which are semirings S which have a star operation defined only on an ideal of S; when the arguments are appropriate, the operation satisfies the above identities. We develop the general theory of partial Conway semirings and prove a Kleene theorem for this generalization.