Axiomatizing the identities of binoid languages

摘要

We present a nontrivial axiomatization for the equational theory of binoid languages, the subsets of a free binoid. In doing so, we prove that a conjecture given in our previous paper was true: the identical laws of ordinary (string) languages, written separately using 'horizontal' and 'vertical' operation symbols form a required complete system of axioms. Among the many fruitful directions in formal language theory, recently there seems to be an increased interest in attempts to generalize the classical theory of string languages to two and more 'dimensions'. Naturally, it is more than reasonable to expect that many links and similarities to the classical theory will be found - and indeed, yet another such link will be discovered in this paper. On the other hand, it occurs quite often that, while investigating the combinatorial and algebraic features of these generalized words and languages, we find ourselves in complicated mathematical situations, without even a distant resemblance to those we know from our (daily) practice with strings and their collections.