The Kleene and the Parikh theorem in complete semirings.

*(English)*Zbl 0625.16026
Automata, languages and programming, Proc. 14th Int. Colloq., Karlsruhe/FRG 1987, Lect. Notes Comput. Sci. 267, 212-225 (1987).

[For the entire collection see Zbl 0616.00013.]

A semiring A is called complete iff for each family \((a_ i|\) \(i\in I)\) with elements \(a_ i\in A\) a sum \(\sum_{i\in I}a_ i\in A\) is defined such that certain axioms are satisfied. As shown by examples, these assumptions are not sufficient to define limits in A by infinite sums. This motivates to call a complete semiring A \(\ell\)-complete iff \(\sum^{n}_{i=0}\alpha (i)=\sum^{n}_{i=0}\beta (i)\) for all \(n\in N\) implies \(\sum^{\infty}_{i=0}\alpha (i)=\sum^{\infty}_{i=0}\beta (i)\) for all sequences \(\alpha,\beta \in A^ N\). Then a natural convergence can be defined in A, and \(a^*\) exists for each \(a\in A\) and \(a^*=\sum^{\infty}_{n=0}a^ n\) holds. However, the limit function of the natural convergence is, in general, not compatible with the partial order on A defined by \(a\leq b\) iff \(a+x=b\) for some \(x\in A\). Thus the corresponding results of Section 5 and 14 of W. Kuich and A. Salomaa [Semirings, Automata, Languages (1986; Zbl 0582.68002)], can not be used for \(\ell\)-complete semirings. However, based on some statements concerning the *-operation in \(\ell\)-complete semirings, the following generalization of the Kleene Theorem is proved in § 3: Let A’ be a subset of an \(\ell\)-complete semiring A that contains 0 and 1. Then the smallest rationally closed semiring \({\mathfrak Rat}(A')\) containing A’ coincides with the rationally closed semiring of the behaviors of A’-finite-automata. The last section is devoted to a corresponding generalization of the Theorem of Parikh (l.c., Thm. 16.36).

A semiring A is called complete iff for each family \((a_ i|\) \(i\in I)\) with elements \(a_ i\in A\) a sum \(\sum_{i\in I}a_ i\in A\) is defined such that certain axioms are satisfied. As shown by examples, these assumptions are not sufficient to define limits in A by infinite sums. This motivates to call a complete semiring A \(\ell\)-complete iff \(\sum^{n}_{i=0}\alpha (i)=\sum^{n}_{i=0}\beta (i)\) for all \(n\in N\) implies \(\sum^{\infty}_{i=0}\alpha (i)=\sum^{\infty}_{i=0}\beta (i)\) for all sequences \(\alpha,\beta \in A^ N\). Then a natural convergence can be defined in A, and \(a^*\) exists for each \(a\in A\) and \(a^*=\sum^{\infty}_{n=0}a^ n\) holds. However, the limit function of the natural convergence is, in general, not compatible with the partial order on A defined by \(a\leq b\) iff \(a+x=b\) for some \(x\in A\). Thus the corresponding results of Section 5 and 14 of W. Kuich and A. Salomaa [Semirings, Automata, Languages (1986; Zbl 0582.68002)], can not be used for \(\ell\)-complete semirings. However, based on some statements concerning the *-operation in \(\ell\)-complete semirings, the following generalization of the Kleene Theorem is proved in § 3: Let A’ be a subset of an \(\ell\)-complete semiring A that contains 0 and 1. Then the smallest rationally closed semiring \({\mathfrak Rat}(A')\) containing A’ coincides with the rationally closed semiring of the behaviors of A’-finite-automata. The last section is devoted to a corresponding generalization of the Theorem of Parikh (l.c., Thm. 16.36).

Reviewer: H.J.Weinert

##### MSC:

16Y60 | Semirings |

68Q70 | Algebraic theory of languages and automata |

68Q45 | Formal languages and automata |

40A05 | Convergence and divergence of series and sequences |

05C05 | Trees |