Semigroups of Terms, Tree Languages, Menger Algebra of <i>n</i>-Ary Functions and Their Embedding Theorems

Abstract

The concepts of terms and tree languages are significant tools for the development of research works in both universal algebra and theoretical computer science. In this paper, we establish a strong connection between semigroups of terms and tree languages, which provides the tools for studying monomorphisms between terms and generalized hypersubstitutions. A novel concept of a seminearring of non-deterministic generalized hypersubstitutions is introduced and some interesting properties among subsets of its are provided. Furthermore, we prove that there are monomorphisms from the power diagonal semigroup of tree languages and the monoid of generalized hypersubstitutions to the power diagonal semigroup of non-deterministic generalized hypersubstitutions and the monoid of non-deterministic generalized hypersubstitutions, respectively. Finally, the representation of terms using the theory of n-ary functions is defined. We then present the Cayley’s theorem for Menger algebra of terms, which allows us to provide a concrete example via full transformation semigroups.

Keywords

• terms
• tree languages
• generalized hypersubstitutions
• <i>n</i>-ary functions