A unifying approach to algebraic systems over semirings (Q2000006)

The introduced unifying approach involves the notion of canonical solutions of algebraic systems of equations in \(\Sigma\)-semirings, which are semirings (algebraic structures with addition and multiplication giving corresponding structures of semigroups) with collections of summable subsets. The introduced canonical solutions of the algebraic equation systems are properly weighted context-free languages, with weights in the semirings. The approach is rather general and effective within continuous or complete semirings. Profiting from the equivalence between weighted CF grammars and weighted pushdown automata, the introduced approach is carried over to this latter class of automata. In its original version, the Chomsky-Schützenberger theorem represents a context-free (CF) language as the meet of a Dyck language (essentially a language consisting of balanced parentheses strings with pairs of left-right parentheses of several kinds) and a regular language. The weighted notions of CF languages and grammars involve weights in the derivation rules. In the paper, the weights of the derivation rules are elements in \(\Sigma\)-semirings. Hence, the introduced approach succeeds in obtaining proper generalizations of the Chomsky-Schützenberger theorem for weighted CF grammars. Certainly, the paper is very interesting for its rather general and unifying scope.