# zbMATH — the first resource for mathematics

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).
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