Narrow Results

We investigate the computational complexity for determining various properties of a finite transformation semigroup given by generators. We introduce a simple framework to describe transformation semigroup properties that are decidable in ${AC}^0$. This framework is then used to show that the problems of deciding whether a transformation semigroup is a group, commutative or a semilattice are in ${AC}^0$. Deciding whether a semigroup has a left (respectively, right) zero is shown to be $NL$-complete, as are the problems of testing whether a transformation semigroup is nilpotent, ${ℛ}$-trivial or has central idempotents. We also give $NL$ algorithms for testing whether a transformation semigroup is idempotent, orthodox, completely regular, Clifford or has commuting idempotents. Some of these algorithms are direct consequences of the more general result that arbitrary fixed semigroup equations can be tested in $NL$. Moreover, we show how to compute left and right identities of a transformation semigroup in polynomial time. Finally, we show that checking whether an element is regular is $PSPACE$-complete.

In a semiprime ring, von Neumann regular elements are determined by their inner inverses. In particular, for elements $a,b$ of a von Neumann regular ring $R$, $a=b$ if and only if $I(a)=I(b)$, where $I(x)$ denotes the set of inner inverses of $x\in R$. We also prove that, in a semiprime ring, the same is true for reflexive inverses.

Let $R$ be a symmetric and $(\alpha ,\delta )$-compatible ring. In this paper, we first specify the zero-divisor elements of the near-ring $R_0[x;\alpha ,\delta ]$. We prove that if $R$ is an $\alpha$-rigid ring, then the set of all zero-divisor elements of the near-ring $R_0[x;\alpha ,\delta ]$ forms an ideal of $R_0[x;\alpha ,\delta ]$ if and only if $Z(R)$ is an ideal of $R$ and $R$ has the right Property $(A)$. Also, we are interested in studying the zero-divisor graph of $R_0[x;\alpha ,\delta ]$ which is denoted by $\mathrm{\Gamma }(R_0[x;\alpha ,\delta ])$. It is shown that $\text{diam}(\mathrm{\Gamma }(R_0[x;\alpha ,\delta ]))\in \{2,3\}$, and if $R$ is not reduced, then ${\mathrm{\text{ann}}}_R(\{a,b\})\cap \text{Nil}(R)\ne 0$ for each $a,b\in Z(R)$ if and only if $\text{diam}(\mathrm{\Gamma }(R_0[x;\alpha ,\delta ]))=2$. Moreover, we characterize the units, the clean elements, the regular elements, the nilpotent elements and also the $\pi$-regular elements of the near-ring $R_0[[x;\alpha ]]$, where $R$ is a reversible and $\alpha$-compatible ring and $\text{Nil}(R)$ is a countable locally nilpotent ideal of $R$. Finally, we prove that the set of all $\pi$-regular elements of $R_0[[x;\alpha ]]$ forms a semigroup, where $R$ is a reversible and $\alpha$-compatible ring and $\text{Nil}(R)$ is a countable locally nilpotent ideal of $R$.

Let be the semigroup of all partial transformations on X, and be the subsemigroups of of all full transformations on X and of all injective partial transformations on X, respectively. Given a non-empty subset Y of X, let , and . In 2008, Sanwong and Sommanee described the largest regular subsemigroup and determined Green's relations of . In this paper, we present analogous results for both and . For a finite set X with |X| ≥ 3, the ranks of , and are well known to be 4, 3 and 3, respectively. In this paper, we also compute the ranks of , and for any proper non-empty subset Y of X.

Let X be any set and P(X) be the partial transformation semigroup on X. It is well-known that P(X) is regular. To generalize this, let X and Y be any sets and P(X, Y) be the set of all partial transformations from X to Y. For θ ∈ P(Y, X), let (P(X, Y), θ) be a semigroup (P(X, Y), *) where α * β = αθβ for all α, β ∈ P(X, Y). In this paper, we characterize the semigroup (P(X, Y), θ) to be regular, regular elements of the semigroup (P(X, Y), θ), -classes, -classes, -classes and -classes of the semigroup (P(X, Y), θ).

Sets of terms of type τ are called tree languages (see [6]). There are several possibilities to define superposition operations on sets of tree languages. On the basis of such superposition operations we define binary associative operations on tree languages and investigate the properties of the arising semigroups. We characterize idempotent and regular elements and Green's relations and . Moreover, we determine constant, left-zero and right-zero subsemigroups and rectangular bands.

It is known that there is a Galois connection between submonoids of the monoid consisting of all hypersubstitutions and complete sublattices of the lattice of all varieties of the same type. It is of interest to know which semigroup properties of hypersubstitutions can be transferred by this Galois connection. In this paper, we characterize regular weak projection hypersubstitutions of all mappings from the set of operation symbols to the set of terms which preserve arities type (2,2).

A mapping σ which assigns to every n-ary cooperation symbol f_i an n_i-ary coterm of type τ = (n_i)_i∈I is said to be a cohypersubstitution of type τ. The concepts of cohypersubstitutions were introduced in [Cohyperidentities and M-solid classes of coalgebras, Discrete Math.309(4) (2009) 772–783]. Every cohypersubstitution σ of type τ induces a mapping on the set of all coterms of type τ. The set of all cohypersubstitutions of type τ under the binary operation which is defined by for all σ₁, σ₂ ∈ Cohyp(τ) forms a monoid which is called the monoid of cohypersubstitution of type τ. In this research, we characterize all idempotent and regular elements of Cohyp(τ) where τ = (3).

A mapping $\sigma$ from $\{f_i|i\in I\}$, the set of all co-operation symbols of type $\tau$, into $C{T}_{\tau }$, the set of all coterms of type $\tau$, is said to be a generalized cohypersubstitution of type $\tau$. Every generalized cohypersubstition $\sigma$ of type $\tau$ induces a mapping $\widehat{\sigma }$ on the set of all coterms of type $\tau$. The set of all generalized cohypersubstitutions of type $\tau$, ${\mathrm{\text{Cohyp}}}_G(\tau )$, under the binary operation ${\circ }_{CG}$, which is defined by ${\sigma }_1{\circ }_{CG}{\sigma }_2:={\widehat{\sigma }}_1\circ {\sigma }_2$ for all ${\sigma }_1,{\sigma }_2\in {\mathrm{\text{Cohyp}}}_G(\tau )$, forms a monoid which is called the monoid of generalized cohypersubstitution of type $\tau$. In this research, we characterize all idempotent and regular elements of ${\mathrm{\text{Cohyp}}}_G(\tau )$, where $\tau =(3)$.

A linear tree language of type $\tau$ is a set of linear terms, terms containing no multiple occurrences of the same variable, of that type. Instead of the usual generalized superposition of tree languages, we define the generalized linear superposition to deal with linear tree languages and study its properties. Using this superposition, we define the product of linear tree languages. This product is not associative on the collection of all linear tree languages, but it is associative on some subsets of this collection whose products of any element in the subsets are nonempty. We classify such subsets and study properties of the obtained semigroup especially idempotent elements, regular elements, and Green’s relations ${ℒ}$ and ${ℛ}$.

A linear tree language of type $\tau$ is a set of linear terms, terms in which each variable occurs at most once, of that type. We investigate a semigroup consisting of the collection of all linear tree languages such that products of any element in the collection are nonempty and the operation of the corresponding linear product especially idempotent elements, Green’s relations ${\mathscr{H}}$, ${𝒟}$, and ${𝒥}$, and some of its subsemigroups. We discover that this semigroup is neither factorizable nor locally factorizable. We also study the linear product iteration and show that any iteration is idempotent in this semigroup. Moreover, we study a semigroup with the complement of the universe set of the above semigroup together with the same linear product operation.

The set of linear terms, i.e. terms in which each variable occurs at most once, does not form a subsemigroup of the so-called diagonal semigroup. We consider the reduct of the diagonal semigroup to the linear terms, which is not a partial semigroup. We extend the set of linear terms by an expression “$\infty$”, that is formally a linear term, obtaining a semigroup. The algebraic structure of this semigroup will be studied in this paper. We characterize the Green’s relations and the regular elements as well as the idempotent elements. Moreover, we discuss the ideal structure.

The set of all $n$-ary terms of type $\tau$ together with a binary operation derived from a superposition $S^n$ forms various forms of semigroups. One may generalize such binary operation by deriving it from an inductive composition of terms and call it an inductive product. However, this operation is not associative on the same base set but it becomes associative when all elements of subterms of a fixed term used in an inductive product except itself are excluded from the base set. Hence, a semigroup is formed. In this paper, we mainly focus on the algebraic structures of this semigroup such as idempotent elements, elements associating with each type of regularity condition, and Green’s relations. The formulae of complexity of inducted terms are also under investigation.

Let $X$ be a nonempty set and let $T(X)$ be the full transformation semigroup on $X$. The main objective of this paper is to study the subsemigroup $\overline{\mathrm{\Omega }}(X,Y)$ of $T(X)$ defined by

In this paper, we construct new $n$-ary semihypergroups induced by subsets of the base sets of $n$-ary semigroups. Then, we investigate some algebraic connections between the $n$-ary semihypergroups and $n$-ary semigroups via the concept of regularity on $n$-ary semihypergroups. We also discover some significant conditions on $n$-ary semihypergroups which can be reduced to semihypergroups.

Let A^⊔n := {1, …, n} × A be the n-th copower of the set A. An n-ary cooperation is a mapping f : A → A^⊔n. If f is an n-ary cooperation and if g₁, …, g_n are k-ary cooperations on A, we may define a composition and obtain a new k-ary cooperation defined on A. Together with the injection cooperations defined by a ↦ (i, a) for 1 ≤ i ≤ n, all cooperations defined on A form a multibased algebra. This algebra is called the clone of all cooperations defined on A. If we define by a binary operation on the set of all n-ary cooperations, the set of all n-ary cooperations defined on A forms a semigroup with respect to this operation. We determine the order of the elements of this semigroup, characterize all idempotent and regular elements, ask for bands of n-ary cooperations and characterize Green's relations and .