On commutative Kleene monoids (Q1176620)

This paper presents a characterization of commutative Kleene monoids. Let \(M\) be a commutative monoid. Let \(S\subset M\). Then \(S\) is recognizable if \(M/\equiv_ S\) is finite, where \(\equiv_ S\) is the syntactic congruence determined by \(S\), namely, \(x\equiv_ Sy\) iff for all \(t\in M\) either \(xt\) and \(yt\) are both in \(S\) or neither is. The set of recognizable subsets of \(M\) is denoted by \(Rec(M)\). The set of rational subsets of \(M\), denoted \(Rat(M)\), is the smallest collection containing the finite subsets and closed under union, concatenation, and Kleene star operations. The monoid \(M\) is called a Kleene monoid if \(Rat(M)=Rec(M)\). It is known that every Kleene monoid is finitely generated. A morphism between monoids is called rational if its graph is a rational subset of the product of the monoids. A monoid \(M\) is said to satisfy the Elgot-Mezei theorem if for any pair of rational morphisms such that one has codomain \(M\) and one has domain \(M\) the composite morphism is also rational. For a monoid \(M\) the set \(U-SSL(S)\) consists of the collection of subsets of \(M\) which are finite disjoint unions of singletons and infinite sets of the form \(\alpha\beta^*\) for \(\alpha,\beta\in M\). The paper then provides two characterization theorems. Theorem 1. For a finitely generated commutative monoid \(M\), the following conditions are equivalent. (1) Every subset \(\alpha\beta^*\) of \(M\) is recognizable. (2) \(U-SSL(M)=Rec(M)\). (3) \(M\) is rational. (4) \(M\) satisfies the Elgot-Mezei theorem. (5) \(M\) is Kleene. Theorem 2. For a finitely generated commutative monoid \(M\), the following conditions are equivalent. (1) \(M\) is Kleene. (2) Every submonoid \(\{\alpha,\beta\}^*\) of \(M\) is Kleene. (3) The group of integers is not homomorphic image of a submonoid of \(M\), i.e., does not divide \(M\).