A KLEENE THEOREM FOR BISEMIGROUP AND BINOID LANGUAGES

摘要

A bisemigroup is a set with two associative operations. Subsets of free bisemigroups are called bisemigroup languages. Recognizable, regular and MSO-definable bisemigroup languages have been studied earlier, and these classes are known to be equal. In this paper we prove a Kleene theorem for bisemigroup languages, namely we show that the class of recognizable bisemigroup languages is the least class which contains the finite languages and closed under the operations of union, horizontal and vertical product, horizontal and vertical iteration, ξ-substitution and a restricted version of the ξ-iteration. We extend our result to binoid languages, i.e., to subsets of free algebras, where the two associative operations share a common identity element.