### Article

KYUNGPOOK Math. J. 2019; 59(4): 617-629

**Published online** December 23, 2019

Copyright © Kyungpook Mathematical Journal.

### The Monoid of Linear Hypersubstitutions

Thawhat Changphas∗, Bundit Pibaljommee and Klaus Denecke

Department of Mathematics, Faculty of Science, Khon Kaen University, Khon Kaen 40002, Thailand

e-mail : thacha@kku.ac.th, banpib@kku.ac.th and klausdenecke@hotmail.com

**Received**: August 22, 2018; **Revised**: December 18, 2018; **Accepted**: December 19, 2018

### Abstract

A term is called linear if each variable which occurs in the term, occurs only once. A hypersubstitution is said to be linear if it maps any operation symbol to a linear term of the same arity. Linear hypersubstitutions have some importance in Theoretical Computer Science since they preserve recognizability [

**Keywords**: linear term, linear hypersubstitution, linear hyperidentity.

### 1. Introduction

The concept of a term is one of the fundamental concepts of algebra. To define terms one needs variables and operation symbols. Let (_{i}_{i}_{∈}_{I}_{i}_{i}_{i}_{i}_{∈}_{I}_{n}_{1}, …, _{n}_{1}, …, _{n}

Let

(i) Every variable _{j}_{n}

(ii) If _{1}, …, _{n}_{i} are _{i}_{i}_{i}_{1}, …, _{n}_{i}) is an

(iii) The set _{τ}_{n}_{1}, …, _{n}

The set of all terms of type

On the set _{τ}_{τ}_{i}_{i}_{i}_{τ}^{ni} → _{τ}_{1}, …, _{n}_{i}) ↦ _{i}_{1}, …, _{n}_{i}) := _{i}_{1}, …, _{n}_{i}). This is possible by (ii) of the definition of terms. Then the pair ℱ(_{τ}_{i}_{i}_{∈}_{I}_{i}_{i}

A term in which each variable occurs at most once, is said to be linear. For a formal definition of

### Definition 1.1

An

(i) _{j}_{n}

(ii) If _{1}, …, _{n}_{i} are _{j}_{k}_{i}_{i}_{1} …, _{n}_{i}) is an

(iii) The set _{1}, …, _{n}

The set of all linear terms of type

The set _{i}_{i}_{1}, …, _{n}_{i}) needs not to be linear if _{1}, …, _{n}_{i}are linear. But, if we define to every _{i}_{i}

then _{i}_{i}_{1}, …, _{n}_{i}) satisfying the condition _{j}_{k}_{i}

Let

if

(Here

The set _{τ}_{1}, …, _{n}_{i}_{1}, …, _{n}_{i}) is an

obtained by replacing the variables _{1}, …, _{n}_{1}, …_{n}_{i} by the terms _{1}, …, _{n}_{i} is a new

Pairs of linear terms are said to be linear equations and if a linear equation is satisfied in an algebra or in a variety of algebras we speak of a linear identity. Linear identities are studied in many papers, see e.g. [1, 3, 9]. Let

be the set of all linear equations of type _{τ}^{2} of all equations of type _{τ}

### Theorem 1.2

_{τ}

**Proof**

Clearly, _{1} ≈ _{1}, …, _{n}_{i} ≈ _{n}_{i} ∈ _{1}, …, _{n}_{i}) ∈ _{i}_{j}_{k}_{i}_{1}, …, _{n}_{i}) ∈ _{i}_{j}_{k}_{i}_{i}_{1}, …, _{n}_{i}) = _{i}_{1}, …, _{n}_{i}) and _{i}_{1}, …, _{n}_{i}) = _{i}_{1}, …, _{n}_{i}). Then from _{i}_{1}, …, _{n}_{i}) ≈ _{i}_{1}, …, _{n}_{i}) ∈ _{τ}^{2} (since _{τ}_{τ}_{i}_{1}, …, _{n}_{i}) ≈ _{i}_{1}, …, _{n}_{i}) ∈ _{τ}

Since linearity of the terms on the left-hand side and the right-hand side of a linear identity can get lost under substitution,

We consider the following example. Let _{(2)}(_{2}) = {_{1} ≈ _{1}, _{1} ≈ _{2}, _{1} ≈ _{1}, _{2}), _{1} ≈ _{2}, _{1}), _{2} ≈ _{1}, _{2} ≈ _{2}, _{2} ≈ _{1}, _{2}), _{2} ≈ _{2}, _{1}), _{1}, _{2}) ≈ _{1}, _{1}, _{2}) ≈ _{2}, _{1}, _{2}) ≈ _{1}, _{2}), _{1}, _{2}) ≈ _{2}, _{1}), _{2}, _{1}) ≈ _{1}, _{2}, _{1}) ≈ _{2}, _{2}, _{1}) ≈ _{1}, _{2}), _{2}, _{1}) ≈ _{2}, _{1})}.

Substituting in _{1} ≈ _{1}, _{2}) for _{1} the linear term _{2}, _{1}) we get _{2}, _{1}) ≈ _{2}, _{1}), _{2}) ∉ _{(2)}(_{2}).

We recall that

### Definition 1.3

A variety _{τ}

Let ^{lin}_{τ}^{lin}

For example, _{1}(_{2}_{3}) ≈ (_{1}_{2})_{3}, _{1}_{2}_{3}_{4} ≈ _{1}_{3}_{2}_{4}}, the variety of medial semigroups, is linear,

For the basic concepts on Universal Algebra see [5] and for partial algebras see [2].

### 2. Linear Hypersubstitutions and Linear Hyperidentities

A mapping _{i}_{τ}_{i}_{i}_{i}_{τ}_{τ}

(i)

(ii) _{i}_{1}, …, _{n}_{i})] = _{i}_{1}], …, _{n}_{i}]) assumed that the results _{j}_{i}

Then a product _{1} ∘_{h}_{2} := _{1} ∘ _{2} can be defined and the set

(This equivalence is called the ‘conjugate property’). For more information on hyperidentities and hypersubstitutions see e.g. [5, 6, 8].

Now we consider hypersubstitutions mapping the operation symbols to linear terms.

### Definition 2.1

A linear hypersubstitution of type

Let ^{lin}

### Example 2.2

Let _{(2)}(_{2}) = {_{1}, _{2}, _{1}, _{2}), _{2}, _{1})} is the set of all binary linear terms of type (2), ^{lin}_{x}_{1}, _{x}_{2}, _{f}_{(}_{x}_{1, }_{x}_{2)} and _{f}_{(}_{x}_{2, }_{x}_{1)}. If we apply the multiplication ∘_{h}_{h}

∘_{h} | _{f}_{(}_{x}_{1, }_{x}_{2)} | _{f}_{(}_{x}_{2, }_{x}_{1)} | _{x}_{1} | _{x}_{2} |

_{f}_{(}_{x}_{1, }_{x}_{2)} | _{f}_{(}_{x}_{1, }_{x}_{2)} | _{f}_{(}_{x}_{2, }_{x}_{1)} | _{x}_{1} | _{x}_{2} |

_{f}_{(}_{x}_{2, }_{x}_{1)} | _{f}_{(}_{x}_{2, }_{x}_{1)} | _{f}_{(}_{x}_{1, }_{x}_{2)} | _{x}_{1} | _{x}_{2} |

_{x}_{1} | _{x}_{1} | _{x}_{2} | _{x}_{1} | _{x}_{2} |

_{x}_{2} | _{x}_{2} | _{x}_{1} | _{x}_{1} | _{x}_{2}. |

Here _{f}_{(}_{x}_{1, }_{x}_{2)} is the identity element of the monoid (^{lin}_{h}_{id}

In the general case it is not clear whether or not the extension

### Lemma 2.3

**Proof**

We give a proof by induction on the complexity of _{i}

Assume that _{i}_{1}, …, _{n}_{i}) and that _{j}_{j}_{i}

by properties of the superposition of terms.

Then we obtain:

### Lemma 2.4

_{i}_{1}, …, _{n}_{i})

_{i}

**Proof**

The previous lemma gives _{l}_{l}_{i}

### Lemma 2.5

**Proof**

Let ^{lin}_{i}_{i}_{i}_{i}_{1}, …, _{n}_{i}), by the previous lemma we have _{j}_{k}_{i}_{1}], …, _{n}_{i}] are linear. Altogether, _{i}_{1}], …, _{n}_{i}]) is linear.

One more consequence is

### Theorem 2.6

(^{lin}_{h}_{id}_{h}_{id}

**Proof**

If _{1}, _{2} ∈ ^{lin}_{1} ∘_{h}_{2} ∈ ^{lin}_{1} ∘_{h}_{2})(_{i}_{1}[_{2}(_{i}_{2}(_{i}_{1} is linear, by the previous lemma _{1}[_{2}(_{i}_{id}_{id}_{i}_{i}_{1}, … _{n}_{i}) is linear.

Now we will give two more examples of linear hypersubstitions.

### Example 2.7

Let _{1}, _{3}), _{2}, _{4})) and _{1}, _{2}). Then ^{lin}

### Example 2.8

Let _{1}, _{3}), _{4})), which maps _{1}, _{2}) and _{1}). Obviously, ^{lin}

The second example shows that there are linear hypersubstitutions which map _{i}_{1}, …, _{n}_{i}}.

As for an arbitrary mapping also for the extension of a hypersubstitution one may consider the kernel of this mapping (see e.g. [8]). In particular, by Lemma 2.4, this can be done for a linear hypersubstitution

### Definition 2.9

Let ^{lin}

is said to be the

For _{τ}_{τ}_{i}_{i}_{∈}_{I}

### Proposition 2.10

^{lin}

**Proof**

_{1}, _{1}) ∈ _{n}_{i}, _{n}_{i}) ∈

Assume that _{i}_{1}, …, _{n}_{i}) and _{i}_{1}, …, _{n}_{i}) exist. Then

and by Lemma 2.3, _{j}_{k}_{j}_{k}_{i}_{i}

Both sides of this equation are linear terms and by the definition of the extension and we obtain

By (

and then

We remark that Theorem 2.6 has important consequences. Let ℳ be an arbitrary submonoid of ℋ

### Definition 2.11

Let be an algebra and let ^{lin}_{lin}

We define an operator

This extends, additively, to sets of identities, so that for any set ∑ of linear identities we set

Using derived algebras we define now an operator

The identity hypersubstitution is linear. Using this, one shows that both operators are extensive, i.e. ^{lin}

Altogether, as for arbitrary monoids of hypersubstitutions, also for linear hypersubstitutions, we have:

### Proposition 2.12

The sets of all fixed points {

The relation ⊨ of satisfaction of an equation as linear identity of an algebra defines the Galois connections (

The relation of linear hypersatisfaction induces a new Galois connection (_{lin}_{lin}

Sets of equations of the form _{lin}_{lin}_{lin}_{lin}_{lin}_{lin}_{τ}^{2} and ℘(

### Theorem 2.13

(i) _{lin}_{lin}

(ii)

(iii) _{lin}

(iv)

(i’) ∑ _{lin}_{lin}

(ii’)

(iii’) _{lin}

(iv’)

From the general theory of conjugate pairs of additive closure operators for

(i)

(ii)

The second proposition can be used if a variety

For any subset of equations and for any monoid ℳ of hypersubstitutions we defined a variety

### Definition 2.14

A variety

Not every identity in a linear-solid variety

### Example 2.15

Let _{1}(_{2}_{3}) ≈ (_{1}_{2})_{3}, _{1}_{2}_{3}_{4} ≈ _{1}_{3}_{2}_{4}} be the variety of medial semigroups. If we apply the four linear hypersubstitutions _{id}_{x}_{1}, _{x}_{2}, _{f}_{(}_{x}_{2, }_{x}_{1)} to each of the both defining identities of variety

### 3. The Monoid of Linear Hypersubstitutions of Type τ n ∣ I ∣

In this section we consider monoids of linear hypersubstitutions when _{i}

To determine all linear hypersubstitutions of this type, we describe the form of

(i) _{i}_{n}

(ii) _{i}_{1}, …, _{n}_{i}) is a composed

### Proposition 3.1

**Proof**

If _{i}_{n}_{i}_{1}, …, _{n}_{i}_{k}_{k}_{k}_{k}_{m}_{l}_{k}_{m}_{l}_{k}_{i}

This observation allows us to describe the form of all

Then it is also clear that there are precisely

Since every linear hypersubstitution maps the operation symbol _{i}_{i}_{j}_{n}_{j}_{s}_{(1)}, …, _{s}_{(}_{n}_{)}) where _{n}

For the product of two linear hypersubstitutions _{1} and _{2} there are precisely the following three possibilities:

1. _{2}(_{i}_{k}_{n}

2. _{2}(_{i}_{j}_{s}_{(1)}, …, _{s}_{(}_{n}_{)}) and _{1}(_{j}_{k}_{1} ∘_{h}_{2})(_{i}_{1}[_{2}(_{i}_{1}[_{j}_{s}_{(1)}, …, _{s}_{(}_{n}_{)})] = _{1}(_{j}_{s}_{(1)}, …, _{s}_{(}_{n}_{)}) = _{s}_{(}_{k}_{)} = _{x}_{s(k)} (_{i}

3. _{2}(_{i}_{j}_{s}_{(1)}, …, _{s}_{(}_{n}_{)}) and _{1}(_{j}_{k}_{s′}_{(1)}, …, _{s′}_{(n)}). Then (_{1}∘_{h}_{2})(_{i}_{1}[_{2}(_{i}_{1}[_{j}_{s}_{(1)}, …, _{s}_{(}_{n}_{)})] = _{1}(_{j}_{s}_{(1)}, …, _{s}_{(}_{n}_{)}) = _{k}_{s′}_{(1)}, …, _{s′}_{(}_{n}_{)})(_{s}_{(1)}, …, _{s}_{(}_{n}_{)}) = _{k}_{(}_{s}_{∘}_{s′}_{)(1)}, …, _{(}_{s}_{∘}_{s′}_{)(}_{n}_{)}).

### 4. Interpretation of Linear Hypersubstitutions on Single Algebras

Term operations induced by linear terms are defined in the usual way. Let

(i)

(ii) if

Here the right-hand side is the superposition of

Let be an algebra of type _{τ}

Let ^{n}

Let ^{n}^{m}

if

The algebra ( ; *,

Now we ask for the algebraic structure of

### Theorem 4.1.([4])

Couceiro and Lehtonen proved in [4] also that the subalgebra _{A}

### Theorem 4.2

^{lin}

**Proof**

1. Φ is well-defined: assume that _{1},

This means .

2. Now we show the compatibility of Φ with the operations

On the other hand we have

This shows . In the same way we obtain .

3. and

4. For the binary operation * we get

### References

- MN. Bleicher, H. Schneider, and RL. Wilson.
Permanence of identities on algebras . Algebra Universalis.,3 (1973), 72-93. - P. Burmeister.
A model theoretic oriented approach to partial algebras . Introduction to theory and application of partial algebras Part I, Mathematical Research,32 , Akademie-Verlag, Berlin, 1986. - I. Chajda, G. Czédli, and R. Halaš.
Tolerances as images of congruences in varieties defined by linear identities . Algebra Universalis.,69 (2013), 167-169. - M. Couceiro, and E. Lehtonen.
Galois theory for sets of operations closed under permutation, cylindrification and composition . Algebra Universalis.,67 (2012), 273-297. - K. Denecke, and SL. Wismath. Hyperidentities and clones,
, Gordon and Breach Science Publishers, Amsterdam, 2000. - SL. Wismath.
The monoid of hypersubstitutions of type (n) . Southeast Asian Bull Math.,24 (1)(2000), 115-128. - F. Gécseg, and M. Steinby. Tree automata,
, Akadémiai Kiadó, Budapest, 1984. - J. Koppitz, and K. Denecke.
M-solid Varieties of algebras . Advances in Mathematics,10 , Springer, New York, 2006. - A. Pilitowska.
Linear identities in graph algebras . Comment Math Univ Carolin.,50 (2009), 11-24. - AI. Mal’cev.
Iterative Algebras and Post’s Varieties . Algebra Logic.,5 (2)(1966), 5-24. - Reichel. M.
Bihomomorphisms and hyperidentities , Dissertation, Universität Potsdam, 1994.