Rational elements of summation semirings (Q2663048)

This paper presents results about the summation semirings of [the author, Theory Comput. Syst. 63, No. 3, 615--633 (2019; Zbl 1431.68067)], also called \(\Sigma\)-semirings by \textit{U. Hebisch} and \textit{H. J. Weinert} [Semirings. Algebraic theory and applications in computer science. Transl. from the German. Singapore: World Scientific Publishing (1998; Zbl 0934.16046)], which generalize complete semirings by allowing summation only on some families of elements. Summation semirings generalize both the notion of complete semiring of [Zbl 1200.68001; Zbl 0934.16046] and of formal power series (with summation over locally finite families) [Zbl 1431.68067]. This paper is therefore a contribution to the research program proposing summation semirings as a potential unifying basis for a large portion of automata theory over semirings. The author first introduces a notion of finite automata over summation semirings that generalizes the automata over complete semirings of \textit{Z. Ésik} and \textit{W. Kuich} [Zbl 1484.68107] and the proper automata of \textit{J. Sakarovitch} [Zbl 1188.68177; Zbl 1484.68110]. The paper then characterizes these automata using star transition matrices, similarly to [Zbl 1200.68001; Zbl 1484.68107; Zbl 1188.68177; Zbl 1484.68110]. However, in the context of summation semirings, it may occur that only one of these approaches is defined, but the author shows that they agree when they both are defined. The finite automata over partial Conway semirings over an ideal of [\textit{S. L. Bloom} et al., Fundam. Inform. 86, No. 1--2, 19--40 (2008; Zbl 1167.08002); \textit{Z. Ésik} and \textit{W. Kuich}, Lect. Notes Comput. Sci. 6570, 76--89 (2011; Zbl 1318.68121)] also unify finite automata over complete semirings and proper automata over semirings of formal power series, but this approach is incomparable to that of this paper. More precisely, the author shows that there is a summation semiring that is not a partial Conway semiring over an ideal, and conversely that there is a partial Conway semiring over an ideal that is not a summation semiring. However, the author states that the settings truly relevant to automata theory are captured by both approaches. The paper then introduces rational expressions, right-linear systems, and monadic second-order logic (MSO) over summation semirings and shows that all these notions are equivalent to the automata previously introduced.