On substructures of semigroups of inductive terms

1.   Introduction

Universal algebra is the study of algebras and classes of algebras of arbitrary type. An important concept of such study is the concept of terms. Terms can be inductively constructed by using variables, elements from the set $X_n = \{x_1, \ldots, x_n\}$ for some positive integer $n$ or the set $X = \{x_1, x_2, x_3, \ldots\}$, each of which is called an alphabet, and non-nullary operation symbols from the set $\{f_i\mid i\in I\}$ where $I$ is an index set. The type $\tau = (n_i)_{i\in I}$ indicates that for each $i\in I$, the operation symbol $f_i$ is $n_i$-ary. The $n$-ary terms of type $\tau$ are inductively defined as follows:

(i) Every variable $t\in X_n$ is an $n$-ary term.

(ii) If $t_1, \ldots, t_{n_i}$ are $n$-ary terms and $f_i$ is an $n_i$-ary operation symbol, then $f_i(t_1, \ldots, t_{n_i})$ is an $n$-ary term.

We denote the set of all $n$-ary terms of type $\tau$ by $W_\tau (X_n)$ and analogously, $W_\tau (X)$ denotes the set of all terms of type $\tau$. Not only terms can be utilized by means of generating a variety of algebras of the same type but they are also applied in many fields especially computer science and linguistics. We refer to ^[2,9,10] for more details on term construction and term advantages in variety formation and ^[2,10,12] on applications of terms in computer science and linguistics.

There are a lot of operations defined on terms, one of which is a superposition of terms. It involves replacing variables in a term by other terms to obtain a new term with the same type. The important trait of superpositions is that they satisfy superassociative law (see e.g., ^[19] for more details). Many forms of superpositions of terms have been discovered during these past years. Generalizing from the superposition $S^n_m$ which is defined on $n$-ary and $m$-ary terms of the same type, the superposition $S^n_g$ defined on $W_\tau (X)$ was introduced by Denecke and Leeratanavalee in ^[7]. As both said superpositions are superassociative, many researchers turned such superpositions into binary operations so that they can be paired with the corresponding set as a base set and form various semigroups. For example, Denecke and Jampachon ^[6] introduced four different binary operations: $+, \ast, +_g$, and $\ast_g$ on the set $W_\tau (X_n)$. There are other forms of superpositions varying with kinds of terms: $S^n$ defined on terms of type $\tau_n$, a sequence with only many $n$ (see ^[3]); $\overline{S}^n_m$ defined on linear terms (see ^[4]); $S^{(k)}_{n, m}$ defined on $k$-terms (see ^[20]); $\overline{S}^n_n$ defined on fixed-length terms (see ^[25]).

Later on, the concept of superpositions was then extended from variable replacement to subterm replacement. For a term $t\in W_\tau (X_n)$, the set $sub(t)$ of all of its subterms is inductively defined as follows (see e.g., ^[12,23,24]):

(i) If $t\in X_n$, then $sub(t) = \{t\}$;

(ii) If $t = f_i (t_1, \ldots, t_{n_i})$, then $sub(t) = \{t\} \cup sub(t_1) \cup \ldots \cup sub(t_{n_i})$.

Shtrakov ^[24] inductively defined the inductive composition which takes advantage of subterm replacement as follows: Let $r, s, t\in W_\tau (X_n)$ be any $n$-ary terms of type $\tau$. The inductive composition $t(r\leftarrow s)$ is the term inductively defined by

(i) $t(r\leftarrow s) = t$ if $r\not\in sub(t)$;

(ii) $t(r\leftarrow s) = s$ if $t = r$;

(iii) $t(r\leftarrow s) = f_i (t_1(r\leftarrow s), \ldots, t_{n_i} (r\leftarrow s))$ if $t = f_i (t_1, \ldots, t_{n_i})$, $r\in sub(t)$, and $t\neq r$.

Concretely interpreted, the term $t(r\leftarrow s)$ is in fact the term in which we simultaneously replace every occurrence of $r$ as a subterm of $t$ by $s$. The readers should notice that $r$ could be any terms in $W_\tau (X_n)$ not only variables. Therefore, the concept of an inductive composition is a generalization of a superposition's one. However, the inductive composition is surprisingly not associative on $W_\tau (X_n)$ in general ^[17]. Then Kitpratyakul and Pibaljommee ^[17] defined a binary operation called inductive product based on fixing a term to be replaced in the inductive composition as follows:

Let $r\in W_{\tau} (X_n)$ be fixed and $s, t \in W_{\tau} (X_n)$. An $r$-inductive product, denoted by $\cdot_r$, is a mapping on $W_{\tau} (X_n)$ defined by

For example, let $\tau = (2, 1, 3)$ with a binary operation symbol $f$, a unary operation symbol $g$, and a ternary operation symbol $h$. Let $r = g(x_3), s = f(x_1, x_4)$, and $t = h(g(x_3), f(x_2, x_4), x_3)$ belong to $W_\tau (X_4)$. Then we have

The inductive product turns out to be a generalization of a term product which is a restriction of a language product defined in ^[8] and ^[12] since the latter performs variable substitution while the former performs subterm replacement.

Semigroups are fundamental algebras which relate to many other kinds of algebras such as monoids, groups, rings, etc. Moreover, they can also be adapted to wording and automata theory (see e.g., ^[2,10,12]). Algebraic structures of semigroups have been studied throughout. In the sense of semigroups of terms, Denecke and Jampachon ^[6] studied the semigroup of $W_\tau (X_n)$ together with four different binary operations: $+, \ast, +_g$, and $\ast_g$. Then Kitpratyakul and Pibaljommee ^[17] investigated the semigroup involving the inductive product and the base set of some restriction on $W_\tau (X_n)$. There are also semigroup studies in other particular contexts of terms such as linear terms or even sets of terms called tree languages. We refer to ^[11,13] for more details on semigroups in general, to ^[21,22] for more details on semigroups of linear terms, and to ^[5,8,16,18] for more details on semigroups of tree languages.

This paper is the sequel of ^[17]. We continue examining the algebraic structures of the same semigroup for its special subsemigroups. The semigroup factorizations are under investigation as well. Moreover, in the remaining sections, we consider a given algebra $W_\tau (X_n)$ and an element $r\in W_\tau (X_n)$ fixed once and for all.

2.   Preliminaries

In this section, we provide, without proofs, some essential findings, lemmas, and theorems concerning inductive products which can be found in ^[17] to be used in later sections.

The first finding is that an algebra $(W_\tau (X_n), \cdot_r)$ is not necessary to be a semigroup. Fortunately, a condition to make it a semigroup is discovered.

Lemma 2.1. Let $s, t, u\in W_\tau (X_n)$. If for any $x, y\in W_\tau (X_n), x\cdot_r y\neq r$ whenever $x\neq r$ or $y\neq r$, then $(t\cdot_r s)\cdot_r u = t\cdot_r (s\cdot_r u)$.

This condition leads to seeking for some maximal subsets of $W_\tau (X_n)$ satisfying such condition and being closed under the operation $\cdot_r$.

Theorem 2.2. The set $W^r _\tau (X_n): = W_\tau (X_n)\setminus (sub(r)\setminus \{r\})$ is a maximal subset of $W_\tau (X_n)$ which is closed under the operation $\cdot_r$ and satisfies the condition: for any $s, t\in W^r _\tau (X_n), t\cdot_r s\neq r$ whenever $s\neq r$ or $t\neq r$.

Thanks to the previous theorem and Lemma 2.1, we eventually obtain the (maximal) semigroup $(W^r _\tau (X_n), \cdot_r)$. Note that the semigroup arising in this way actually becomes $(W_\tau (X_n), \cdot_r)$ whenever $r\in X_n$. Furthermore, $(W^r _\tau (X_n), \cdot_r)$ is in fact a monoid with $r\in W^r_\tau (X_n)$ as its identity which can be easily seen that $r\cdot_r t = t = t\cdot_r r$ for any term $t\in W^r_\tau (X_n)$.

We then present complexity measurements of an inductive term, four of which are the maximum depth, the minimum depth, the variable count, and the operation-symbol count. In this paper, we often consider the operation-symbol count of terms. For a term $t\in W^r_\tau (X_n)$, its operation-symbol count $op(t)$ is inductively defined by

(i) $op(t) = 0$ if $t\in X_n$;

(ii) $1+ \sum\limits^{n_i} _{j = 1} op(t_j)$ if $t = f_i (t_1, \ldots, t_{n_i})$.

There is also a formula of the operation-symbol count of an inductive term $t\cdot_r s$ by which we denote $op(t\cdot_r s)$. Here, for any term $r, t\in W_{\tau} (X_n)$, let $n_r (t)$ be the number of $r$ occurring as subterms of $t$. Note that $n_r (t\cdot_r s) = n_r (t) \cdot n_r (s)$ for all $s, t\in W_\tau (X_n)$.

To clarify the definition of $op(t)$ and $n_r (t)$, we give an example. Consider $W_\tau (X_4)$ where $\tau = (2, 1)$, $f$ and $g$ are binary and unary operation symbols, respectively, and $r = g(x_2)$. We obtain the following values.

Theorem 2.3. Let $s, t, t_1, \ldots, t_m\in W_{\tau} (X_n)$. Then

(i) $op(t\cdot_r s) = op(t)+ n_r (t) (op(s)-op(r))$;

(ii) $op(t_1\cdot_r t_2\cdot_r \ldots \cdot_r t_m) = op(t_1)+ \sum\limits_{k = 1} ^{m-1} n_r (t_1\cdot_r t_2\cdot_r \ldots \cdot_r t_k)(op(t_{k+1})-op(r))$.

We refer to ^[17] for the other complexities of an inductive term.

Next, we present beneficial lemmas of an $r$-inductive product on the set $W^r _\tau (X_n)$.

Lemma 2.4. Let $s, t\in W^r _\tau (X_n)$. Then

(i) If $r\in sub(t)$, then $sub(s)\subseteq sub(t\cdot_r s)$;

(ii) If $r\not\in sub(t)$, then $t\cdot_r s = t$;

(iii) $r\in sub(t)$ and $r\in sub(s)$ if and only if $r\in sub(t \cdot_r s)$;

(iv) $t = r$ and $s = r$ if and only if $t \cdot_r s = r$.

In a semigroup, idempotents and regular elements play traditionally a prominent role. An element $t\in (W^r_\tau (X_n), \cdot_r)$ is called idempotent if $t\cdot _r t = t$ and $t$ is called regular if there is an element $s\in (W^r_\tau (X_n), \cdot_r)$ such that $t = t \cdot_r s \cdot_r t$. Characterizations of both said elements in the semigroup $(W^r_\tau (X_n), \cdot_r)$ are given as follows.

Theorem 2.5. Let $t\in W^r_\tau (X_n)$. Then the following statements are equivalent.

(i) $t$ is idempotent.

(ii) $t$ is regular.

(iii) $r\not\in sub(t)$ or $t = r$.

The next lemma can be used in determination of a finite inductive product.

Lemma 2.6. Let $t\in W^r _\tau (X_n)$. Assume that $t = t_1\cdot_r t_2\cdot_r \ldots \cdot_r t_m$ for some $t_1, \ldots, t_m \in W^r _\tau (X_n)$. Then

(i) If at least two of $t_j\mathit{{\rm{'}}} s$ are $t$, then $t$ is idempotent;

(ii) If there is the unique term $t'_j\in \{t_1, \ldots, t_m\}$ such that $t'_j = t$, then $t$ can be any element of $W^r _\tau (X_n)$.

Finally, all regularity conditions of the semigroup $(W^r_\tau (X_n), \cdot_r)$ are described in the next lemma.

Theorem 2.7. Let $R\subseteq W^r _\tau (X_n)$ be any set of all terms satisfying a fixed kind of regularity conditions for $(W^r _\tau (X_n), \cdot_r)$. Then either $R = W^r _\tau (X_n)$ or $R = \{r\}\cup \{t\in W^r _\tau (X_n) \mid r\not\in sub(t)\}$.

To avoid writing repetition in later sections, we would like to remind that the characterization of a term $t\in W^r _\tau (X_n)$ must always include $t\not\in sub(r)\setminus \{r\}$. The readers should recognize such condition even if it is not mentioned.

3.   Special subsemigroups of $(W^r _\tau (X_n), \cdot_r)$

In this section, we characterize interesting subsemigroups of $(W^r _\tau (X_n), \cdot_r)$ such as constant, left-zero, right-zero, regular, and inverse subsemigroups, as well as bands, rectangular bands, and subgroups. We recall their definitions here.

Definition 3.1. A subsemigroup $(S, \cdot_r)$ of $(W^r _\tau (X_n), \cdot_r)$ is said to be:

$(i)$ constant if there is $k\in S$ such that $t\cdot_r s = k$ for any $s, t \in S$;

(ii) left-zero if $t\cdot_r s = t$ for any $s, t \in S$;

(iii) right-zero if $t\cdot_r s = s$ for any $s, t \in S$;

(iv) a band if $t\cdot_r t = t$ for any $t \in S$;

(v) regular if for each $t \in S$, $t\cdot_r s\cdot_r t = t$ for some $s\in S$;

(vi) a rectangular band if $t\cdot_r s\cdot_r t = t$ for any $s, t \in S$;

(vii) inverse if for each $t\in S$, there is the unique $t'\in S$ such that $t\cdot_r t'\cdot_r t = t$ and $t'\cdot_r t\cdot_r t' = t'$;

(viii) a subgroup if $(S, \cdot_r)$ is a group.

It is important to note from Theorem 2.5 that bands and regular subsemigroups coincide in the semigroup $(W^r _\tau (X_n), \cdot_r)$.

We start with a characterization of a band (a regular subsemigroup) which should probably be easy to handle since we have known the classification of all idempotents in $(W^r _\tau (X_n), \cdot_r)$ from Theorem 2.5. We denote $E_n$ to be the set of all idempotent elements in $(W^r _\tau (X_n), \cdot_r)$. To get a band, we need to find a subset of $E_n$ which is also a semigroup under $\cdot_r$. In fact, we have the following theorem.

Theorem 3.2. Let $\emptyset\neq A\subseteq E_n$. Then $(A, \cdot_r)$ is a subsemigroup of $(W^r _\tau (X_n), \cdot_r)$.

Proof. Let $s, t\in A\subseteq E_n$. By Theorem 2.5, we have that $r\not\in sub(s)$ or $s = r$ and the same argument holds for $t$. If $r\not\in sub(s)$, then $s\cdot_r t = s \in A$. If $s = r$, then $s\cdot_r t = t \in A$. Therefore, $(A, \cdot_r)$ is a subsemigroup of $(W^r _\tau (X_n), \cdot_r)$.

We now have the following corollary describing all bands (all regular subsemigroups) in $(W^r _\tau (X_n), \cdot_r)$.

Corollary 3.3. Let $S\subseteq W^r _\tau (X_n)$. Then $S$ is a band if and only if it is a nonempty subset of $\{r \} \cup \{t\in W^r _\tau (X_n) \mid r\not\in sub(t) \}$.

An $E$-semigroup is a semigroup in which the set of all idempotents forms a subsemigroup (see e.g., ^[1]). By setting $A$ in Theorem 3.2 to be $E_n$, we obtain the following corollary.

Corollary 3.4. The semigroup $(W^r _\tau (X_n), \cdot_r)$ is an $E$-semigroup.

There are six kinds of subsemigroups left to be characterized. It appears that there are two main distinct characterizations. Before we start with the first one, we need the following two lemmas.

Lemma 3.5. Let $t\in W^r_\tau (X_n)$ such that $r\in sub(t)$. Then $op(t)\geq n_r (t) \cdot op(r)$. This inequality is an equality if and only if $t = r$.

Proof. The proof takes on the structure of $t$. If $t = r$, then $n_r (t) = 1$ and hence $op(t) = op(r) = n_r (t) \cdot op(r)$. For $t = f_i (t_1, \ldots, t_{n_i})\neq r$, we inductively assume that $op(t_j)\geq n_r (t_j) \cdot op(r)$ for each $t_j\in \{t_1, \ldots, t_{n_i}\}$ such that $r\in sub(t_j)$. Note that for any $t_l\in \{t_1, \ldots, t_{n_i}\}$ such that $r\not\in sub(t_l)$, we get $n_r (t_l) = 0$ and so $op(t_l)\geq 0 = n_r(t_l)\cdot op(r)$. The formula of operation-symbol count yields

The numbers $1$ in the above expression are significant as they deduce a strict inequality for $t = f_i (t_1, \ldots, t_{n_i})\neq r$. Therefore, the equality claim is valid.

We remark on the above lemma that the condition of $t$ to have $r$ as its subterms may be omitted and we still have the inequality. We decide not to include such case in the lemma because the equality condition will be too complicated to use. Besides, the above lemma is useful in aiding the proof of the following lemma.

Lemma 3.6. Let $s, t\in W^r_\tau (X_n)$. If $t = s\cdot_r t$, then $s = r$ or $s = t$.

Proof. Assume that $t = s\cdot_r t$. If $r\not\in sub(s)$, then $s = s\cdot_r t = t$. If $r\in sub(s)$, then $n_r (s) \geq 1$ and $op(s)\geq op(r)$. Both $t = s\cdot_r t$ and the formula of Theorem 2.3 (i) provide $op(t) = op(s\cdot_r t) = op(s) + n_r (s) (op(t)-op(r)) = n_r (s)\cdot op(t) + (op(s)- n_r (s)\cdot op(r))$. This implies by Lemma 3.5 that $(1-n_r (s))op(t) = op(s)- n_r (s)\cdot op(r) \geq 0$. If $op(t) = 0$, then $op(s)- n_r (s)\cdot op(r) = 0$. By Lemma 3.5, we obtain $s = r$. If $op(t) > 0$, then $1-n_r (s) \geq 0$; in other words, $n_r (s)\leq 1$. Together with $n_r (s) \geq 1$, we actually have $n_r (s) = 1$ to which case leads $op(s)- n_r (s)\cdot op(r) = 0$. Lemma 3.5 again brings $s = r$.

The first main characterization is now ready to be given in the next theorem.

Theorem 3.7. Let $\emptyset \neq S\subseteq W^r _\tau (X_n)$. Then the following statements are equivalent.

(i) $(S, \cdot_r)$ is a constant subsemigroup of $(W^r_\tau (X_n), \cdot_r)$.

(ii) $(S, \cdot_r)$ is a right-zero subsemigroup of $(W^r_\tau (X_n), \cdot_r)$.

(iii) $(S, \cdot_r)$ is a subgroup of the semigroup $(W^r_\tau (X_n), \cdot_r)$.

(iv) $S = \{s\}$ with $s\in E_n$.

Proof. Obviously, if the statement (iv) holds, the others also hold. Next, we show that if we have (i), (ii), or (iii), we obtain (iv).

(i) $\Rightarrow$ (iv) Assume that $(S, \cdot_r)$ is a constant subsemigroup of $(W^r_\tau (X_n), \cdot_r)$. Let $s, t\in S$. Then $t \cdot_r s = u$ for some $u\in S$ which is independent of $s$ and $t$. We also have $s \cdot_r t = u$. We need to show that $s = t$. We do so by considering two cases: $r\not\in sub(t)$ and $r\in sub(t)$. For the case $r\not\in sub(t)$, we have $u = t\cdot_r s = t$. So, $s\cdot_r t = t$. By Lemma 3.6, we obtain $s = r$ or $s = t$. However, $s = r$ could imply $r\cdot_r r = t$ which means that $t = r$, a contradiction to $r\not\in sub(t)$. Therefore, $s = t$. For another case, $r\in sub(t)$, the expression $t\cdot_r t = u$ implies by Lemma 2.4 (iii) that $r\in sub(u)$. Since $u\cdot_r u = u$, $u$ is an idempotent. By Theorem 2.5 and $r\in sub(u)$, we get $u = r$. By Lemma 2.4 (iv), the equation $t\cdot_r s = u = r$ implies $s = r = t$. These show that $S$ is a singleton set. Also, for any $t\in S$, we have $t\cdot_r t = t$, so it is idempotent.

(ii) $\Rightarrow$ (iv) Assume that $S\subseteq W^r_\tau (X_n)$ is a right-zero semigroup. Let $s, t\in S$. Then $t\cdot_r s = s$ and $s\cdot_r t = t$. It follows that $t\cdot_r s\cdot_r t = t$. Lemma 2.6 (i) yields idempotency of $t$. By Theorem 2.5, $t = r$ or $r\not\in sub(t)$. The former case gives $t = s\cdot_r t = s$ while the latter provides $s = t\cdot_r s = t$. These show that $S$ is a singleton set of an idempotent in $(W^r _\tau (X_n), \cdot_r)$.

(iii) $\Rightarrow$ (iv) Assume that $S\subseteq W^r _\tau (X_n)$ is a group. Let $s, t\in S$. There exists an identity $i\in S$ such that $t\cdot_r i = t = i\cdot_r t$ and $s\cdot_r i = s = i\cdot_r s$. By Lemma 3.6, we have $i = r$ or $i = t$. If $i = r$, then by the inverse property of $S$, there exist $a, b\in S$ such that $t\cdot_r a = i = r$ and $s\cdot_r b = i = r$. It follows from Lemma 2.4 (iv) that $t = r = s$, i.e., $t = s = r = i$. For $i = t$, we have $s = t\cdot_r s$ and Lemma 3.6 provides that $t = r$ or $t = s$. Both possibilities give $s = t = i$. Apparently, the identity $i$ of $S$ belongs to $E_n$.

The second characterization of subsemigroups of $(W^r_\tau (X_n), \cdot_r)$ is presented in the next theorem.

Theorem 3.8. Let $\emptyset\neq S\subseteq W^r_\tau (X_n)$. Then the following statements are equivalent.

(i) $(S, \cdot_r)$ is a left-zero subsemigroup of $(W^r_\tau (X_n), \cdot_r)$.

(ii) $(S, \cdot_r)$ is a rectangular band.

(iii) Either $S = \{r\}$ or $S\subseteq \{t\in W^r_\tau (X_n)\mid r\not\in sub(t) \}$.

Proof. It is easy to see that the statement (iii) implies the rest. Also, (i) $\Rightarrow$ (ii) is obvious. Next, we show (ii) $\Rightarrow$ (iii). Assume that $S$ is a rectangular band. Let $t\in S$. Then $t = t\cdot_r s\cdot_r t$ for any $s\in S$. By Lemma 2.6 (i), we have that $t$ is idempotent. Then by Theorem 2.5, we obtain $t = r$ or $r\not\in sub(t)$. For $t = r$, we have $r = r\cdot_r s\cdot_r r = s$ for any $s\in S$. The first equation comes from $S$ being a rectangular band while the second equation is a result of the identity $r$. Hence, $S = \{r\}$. For $r\not\in sub(t)$, we get $S\subseteq \{t\in W^r_\tau (X_n)\mid r\not\in sub(t) \}$.

The last type of subsemigroups in our interest, an inverse subsemigroup, is characterized in the next theorem.

Theorem 3.9. Let $\emptyset\neq S\subseteq W^r_\tau (X_n)$. Then $(S, \cdot_r)$ is an inverse subsemigroup of $(W^r_\tau (X_n), \cdot_r)$ if and only if either $S = \{s\}$ with $s\in E_n$ or $S = \{r, t\}$ for some $t\in W^r_\tau (X_n)$ with $r\not\in sub(t)$.

Proof. We first prove the necessary condition. A singleton set of an idempotent is unquestionably an inverse semigroup with respect to $\cdot_r$. Assume that $S = \{r, t\}$ for some $t\in W^r_\tau (X_n)$ such that $r\not\in sub(t)$. To show that $r$ and $t$ have the unique inverse element. Let $r'$ be an inverse of $r$. Then $r = r\cdot_r r'\cdot_r r = r'$ and so the only inverse of $r$ is $r$ itself. For $t$, we notice that $t$ is an idempotent due to Theorem 2.5, and hence it is an inverse of itself. This inverse is unique because $r$ does not have $t$ as an inverse. Therefore, $S$ is an inverse semigroup with respect to $\cdot_r$. Conversely, assume that $S$ is an inverse subsemigroup of $(W^r_\tau (X_n), \cdot_r)$. Let $t\in S$. Then $t$ has the unique inverse, says $t^{-1}$. It follows that $t\cdot_r t^{-1}\cdot_r t = t$ and $t^{-1}\cdot_r t\cdot_r t^{-1} = t^{-1}$. By Lemma 2.6 (i), $t$ is an idempotent element. If $\vert S\vert = 1$, then $S$ is a singleton set of an idempotent $(W^r_\tau (X_n), \cdot_r)$. For $\vert S\vert = 2$, we let $s\in S\setminus\{t\}$. Then Theorem 2.5 provides that $t = r$ or $r\not\in sub(t)$ and $s = r$ or $r\not\in sub(s)$, by which we have three possible cases:

Case 1: $t = r$ and $s = r$. This contradicts $s\in S\setminus\{t\}$.

Case 2: $t = r$ and $r\not\in sub(s)$. This is actually what we have shown in the necessary condition.

Case 3: $r\not\in sub(t)$ and $r\not\in sub(s)$. Then by Lemma 2.4 (ii), we have $t = t\cdot_r s\cdot_r t$ and $s = s\cdot_r t\cdot_r s$. These mean that $t$ and $s$ are inverses of each other. Since both $t$ and $s$ are idempotent, each of them must be an inverse of itself. By uniqueness of invertibility, we obtain $t = s$ yet contradicts $s\in S\setminus\{t\}$.

If $\vert S\vert\geq 3$, then there exist $u, v\in S$ such that $u\neq v, u\neq r$, and $v\neq r$. With the help of Theorem 2.5, idempotency of $u$ and $v$ gives $r\not\in sub(u)$ and $r\not\in sub(v)$. These contexts are the same as the one in Case $3$ of $\vert S\vert = 2$ above, so we actually get a contradiction.

4.   (Global) factorization and local factorization of the semigroup $(W^r _\tau (X_n), \cdot_r)$

In this section, we study two kinds of factorizations of the semigroup $(W^r _\tau (X_n), \cdot_r)$: factorization and locally factorization, each of which mainly focuses on idempotents and subgroups of the semigroup. We refer to ^[14,15] for more information on factorization and locally factorization in general semigroups. Recall that for any semigroup $S$ and nonempty subsets $M$ and $N$ of $S$, we define

If we deal with a singleton set, says $\{a\}$, we may write $Ma$ and $aN$ instead of $M\{a\}$ and $\{a\}N$, respectively.

We continue using the notation $E_n$ as the set of all idempotent elements in $(W^r_\tau (X_n), \cdot_r)$. A local subsemigroup of $W^r_\tau (X_n)$ is a subsemigroup of the form $e\cdot_r W^r_\tau (X_n)\cdot_r e$ for some $e\in E_n$.

It is worth remarking that the inclusion $E_n\subset W^r_\tau (X_n)$ with respect to $\cdot_r$ is strict. We can always find a term $t\in W^r_\tau (X_n)$ with $r\in sub(t)$ and $op(t) > op(r)$ since $\tau$ contains no zero arity and $r$ is a fixed term in $W^r_\tau (X_n)$. Such a term does not appear to be idempotent due to Theorem 2.5.

The semigroup $W^r_\tau (X_n)$ will be left [right] factorizable if $W^r_\tau (X_n) = G\cdot_r E_n$ [$W^r_\tau (X_n) = E_n\cdot_r G$] for some subgroup $G$ of $W^r_\tau (X_n)$. Naturally, the semigroup $W^r_\tau (X_n)$ will be factorizable if it is both left and right factorizable. The semigroup $W^r_\tau (X_n)$ will be locally factorizable if each of its local subsemigroups is factorizable.

Thanks to Theorem 3.7, any subgroup of $(W^r_\tau (X_n), \cdot_r)$ is of the form $(\{t\}, \cdot_r)$ for some idempotent $t\in W^r_\tau (X_n)$. So, in order to consider factorizability of $W^r_\tau (X_n)$, we need to find idempotents $e_1$ and $e_2$ such that $W^r_\tau (X_n) = e_1\cdot_r E_n$ and $W^r_\tau (X_n) = E_n\cdot e_2$. The next theorem shows that there are no such idempotents.

Theorem 4.1. The semigroup $(W^r_\tau (X_n), \cdot_r)$ is neither left factorizable nor right factorizable.

Proof. Suppose that $W^r_\tau (X_n)$ is left factorizable. Then there exists $e\in E_n$ such that $W^r_\tau (X_n) = e\cdot_r E_n$. By Theorem 2.5, we have $e = r$ or $r\not\in sub(e)$. If $e = r$, then $W^r_\tau (X_n) = e\cdot_r E_n = E_n$, a contradiction. If $r\not\in sub(e)$, then $W^r_\tau (X_n) = e\cdot_r E_n = \{e\}$, a contradiction. So, $W^r_\tau (X_n)$ is not left factorizable. Next, suppose that $W^r_\tau (X_n)$ is right factorizable. Then there is $f\in E_n$ such that $W^r_\tau (X_n) = E_n\cdot_r f$. $f$ is of the form $f = r$ or $r\not\in sub(f)$ by Theorem 2.5. It is a routine matter to show that both forms of $f$ provide that $E_n\cdot_r f\subseteq E_n \neq W^r_\tau (X_n)$, a contradiction. Hence, $W^r_\tau (X_n)$ is not right factorizable.

The proof of this theorem can be achieved in a simpler alternative approach using Theorem 3.2 and 3.7. We actually have $G\cdot_r E_n = \{e\}\cdot_r E_n \subseteq E_n \neq W^r_\tau (X_n)$ and $E_n\cdot_r H = E_n\cdot \{e\} \subseteq E_n \neq W^r_\tau (X_n)$ for any subgroups $G$ and $H$ which are singleton sets of an idempotent. Therefore, $W^r_\tau (X_n)$ is neither left nor right factorizable.

It is natural to ask for a maximal subsemigroup of $(W^r_\tau (X_n), \cdot_r)$ which is factorizable.

Theorem 4.2. $(E_n, \cdot_r)$ is the maximal subsemigroup of $(W^r_\tau (X_n), \cdot_r)$ which is factorizable.

Proof. By Theorem 3.2, $E_n$ is a subsemigroup of $W^r_\tau (X_n)$. Theorem 3.7 provides an easy illustration of factorizability of $E_n$, that is, $E_n\cdot_r \{r\} = E_n = \{r\}\cdot_r E_n$. Maximality can be obtained from what we have shown in the alternative proof of Theorem 4.1 above.

Due to Theorem 2.5, local subsemigroups of $W^r_\tau (X_n)$ are of the forms $r\cdot_r W^r_\tau (X_n)\cdot_r r = W^r_\tau (X_n)$ or $e\cdot_r W^r_\tau (X_n)\cdot_r e = \{e\}$ for some $e\in W^r_\tau (X_n)$ such that $r\not\in sub(e)$. As a consequence, we have the following theorem.

Theorem 4.3. Let $e\in E_n$. Then a local subsemigroup $e\cdot_r W^r_\tau (X_n) \cdot_r e$ of $W^r_\tau (X_n)$ is factorizable if and only if $r\not\in sub(e)$.

Then we directly have the following corollary.

Corollary 4.4. $(W^r_\tau (X_n), \cdot_r)$ is not locally factorizable.

5.   Conclusions

In this paper, we characterized substructures of the semigroups of inductive terms consisting of an inductive product as the binary operation and the base set of all $n$-ary terms of type $\tau$ excluding the proper subterms of the corresponding fixed term from the product. It turns out that there are three kinds of coincidences: bands and regular subsemigroups; subgroups, right-zero subsemigroups, and constant subsemigroups; rectangular bands and left-zero subsemigroups. Meanwhile, inverse subsemigroups take similar but not exact forms of the above mentioned substructures. These semigroups of inductive terms are neither factorizable nor locally factorizable. However, we managed to find the condition of a maximal subsemigroup to be factorizable as well as the condition to render some local subsemigroups factorizable. Possible directions of future works are to study other properties of these semigroups and one may try to define other binary operations concerning inductive compositions and characterize their algebraic properties as well as those of arising semigroups.

Acknowledgments

Bundit Pibaljommee has received funding support from the National Science, Research and Innovation Fund (NSRF). The authors also deeply appreciate the referees for the precious suggestions.

Conflict of interest

All authors declare no conflicts of interest in this paper.