Multi-solid varieties and Mh-transducers

We consider the concepts of colored terms and multi-hypersubstitutions. If t∈Wτ(X) is a term of type τ, then any mapping αt:PosF(t)→N of the non-variable positions of a term into the set of natural numbers is called a coloration of t. The set Wcτ(X) of colored terms consists of all pairs ⟨t,αt⟩....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2007
Автор:	Shtrakov, S.
Формат:	Стаття
Мова:	English
Опубліковано:	Інститут прикладної математики і механіки НАН України 2007
Назва видання:	Algebra and Discrete Mathematics
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/152366
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Multi-solid varieties and Mh-transducers / S. Shtrakov // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 3. — С. 113–131. — Бібліогр.: 10 назв. — англ.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-152366
record_format	dspace
spelling	irk-123456789-1523662019-06-11T01:25:24Z Multi-solid varieties and Mh-transducers Shtrakov, S. We consider the concepts of colored terms and multi-hypersubstitutions. If t∈Wτ(X) is a term of type τ, then any mapping αt:PosF(t)→N of the non-variable positions of a term into the set of natural numbers is called a coloration of t. The set Wcτ(X) of colored terms consists of all pairs ⟨t,αt⟩. Hypersubstitutions are maps which assign to each operation symbol a term with the same arity. If M is a monoid of hypersubstitutions then any sequence ρ=(σ1,σ2,…) is a mapping ρ:N→M, called a multi-hypersubstitution over M. An identity t≈s, satisfied in a variety V is an M-multi-hyperidentity if its images ρ[t≈s] are also satisfied in V for all ρ∈M. A variety V is M-multi-solid, if all its identities are M−multi-hyperidentities. We prove a series of inclusions and equations concerning M-multi-solid varieties. Finally we give an automata realization of multi-hypersubstitutions and colored terms. 2007 Article Multi-solid varieties and Mh-transducers / S. Shtrakov // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 3. — С. 113–131. — Бібліогр.: 10 назв. — англ. 1726-3255 2000 Mathematics Subject Classification:08B15, 03C05, 08A70. http://dspace.nbuv.gov.ua/handle/123456789/152366 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
description	We consider the concepts of colored terms and multi-hypersubstitutions. If t∈Wτ(X) is a term of type τ, then any mapping αt:PosF(t)→N of the non-variable positions of a term into the set of natural numbers is called a coloration of t. The set Wcτ(X) of colored terms consists of all pairs ⟨t,αt⟩. Hypersubstitutions are maps which assign to each operation symbol a term with the same arity. If M is a monoid of hypersubstitutions then any sequence ρ=(σ1,σ2,…) is a mapping ρ:N→M, called a multi-hypersubstitution over M. An identity t≈s, satisfied in a variety V is an M-multi-hyperidentity if its images ρ[t≈s] are also satisfied in V for all ρ∈M. A variety V is M-multi-solid, if all its identities are M−multi-hyperidentities. We prove a series of inclusions and equations concerning M-multi-solid varieties. Finally we give an automata realization of multi-hypersubstitutions and colored terms.
format	Article
author	Shtrakov, S.
spellingShingle	Shtrakov, S. Multi-solid varieties and Mh-transducers Algebra and Discrete Mathematics
author_facet	Shtrakov, S.
author_sort	Shtrakov, S.
title	Multi-solid varieties and Mh-transducers
title_short	Multi-solid varieties and Mh-transducers
title_full	Multi-solid varieties and Mh-transducers
title_fullStr	Multi-solid varieties and Mh-transducers
title_full_unstemmed	Multi-solid varieties and Mh-transducers
title_sort	multi-solid varieties and mh-transducers
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2007
url	http://dspace.nbuv.gov.ua/handle/123456789/152366
citation_txt	Multi-solid varieties and Mh-transducers / S. Shtrakov // Algebra and Discrete Mathematics. — 2007. — Vol. 6, № 3. — С. 113–131. — Бібліогр.: 10 назв. — англ.
series	Algebra and Discrete Mathematics
work_keys_str_mv	AT shtrakovs multisolidvarietiesandmhtransducers
first_indexed	2025-07-13T02:55:28Z
last_indexed	2025-07-13T02:55:28Z
_version_	1837498718074437632
fulltext	Jo u rn al A lg eb ra D is cr et e M at h . Algebra and Discrete Mathematics RESEARCH ARTICLE Number 3. (2007). pp. 113 – 131 c© Journal “Algebra and Discrete Mathematics” Multi-solid varieties and Mh-transducers Slavcho Shtrakov Communicated by B. V. Novikov Abstract. We consider the concepts of colored terms and multi-hypersubstitutions. If t ∈ Wτ (X) is a term of type τ , then any mapping αt : PosF (t) → IN of the non-variable positions of a term into the set of natural numbers is called a coloration of t. The set W c τ (X) of colored terms consists of all pairs 〈t, αt〉. Hy- persubstitutions are maps which assign to each operation symbol a term with the same arity. If M is a monoid of hypersubstitutions then any sequence ρ = (σ1, σ2, . . .) is a mapping ρ : IN→M , called a multi-hypersubstitution over M . An identity t ≈ s, satisfied in a variety V is an M -multi-hyperidentity if its images ρ[t ≈ s] are also satisfied in V for all ρ ∈ M . A variety V is M -multi-solid, if all its identities are M−multi-hyperidentities. We prove a series of inclusions and equations concerning M -multi-solid varieties. Fi- nally we give an automata realization of multi-hypersubstitutions and colored terms. Introduction Let F be a set of operation symbols, and τ : F → N be a type or signature. Let X be a finite set of variables, then the set Wτ (X) of terms of type τ with variables from X is the smallest set, such that (i) X ∪ F0 ⊆Wτ (X); (ii) if f is n−ary operation symbol and t1, . . . , tn are terms, then the “string" f(t1 . . . tn) is a term. An algebra A = 〈A;FA〉 of type τ is a pair consisting of a set A and a set FA of operations defined on A. If f ∈ F , then fA denotes a τ(f)-ary 2000 Mathematics Subject Classification: 08B15, 03C05, 08A70. Key words and phrases: Colored term; multi-hypersubstitution; deduction of identities. Jo u rn al A lg eb ra D is cr et e M at h .114 Multi-Solid Varieties and Mh-transducers operation on the set A. An identity s ≈ t is satisfied in the algebra A (written A \|= s ≈ t), if sA = tA. Alg(τ) denotes the class of all algebras of type τ and Id(τ) - the set of all identities of type τ. The pair (Id,Mod) is a Galois connection between the classes of algebras from Alg(τ) and subsets of Id(τ), where Id(R) := {t ≈ s \|∀A ∈ R, (A \|= t ≈ s)} and Mod(Σ) := {A\|∀t ≈ s ∈ Σ, (A \|= t ≈ s)}. The fixed points with respect to the closure operators IdMod and ModId form complete lattices L(τ) := {R \| R ⊆ Alg(τ) and ModIdR = R} and E(τ) := {Σ \| Σ ⊆ Id(τ) and IdModΣ = Σ} of all varieties of type τ and of all equational theories (logics) of type τ . These lattices are dually isomorphic. A hypersubstitution of type τ (briefly a hypersubstitution) is a map- ping which assigns to each operation symbol f ∈ F a term σ(f) of type τ , which has the same arity as the operation symbol f (see [5]). The set of all hypersubstitutions of type τ is denoted byHyp(τ). If σ is a hypersubstitu- tion, then it can be uniquely extended to a mapping σ̂ : Wτ (X)→Wτ (X) on the set of all terms of type τ , as follows (i) if t = xj for some j ≥ 1, then σ̂[t] = xj ; (ii) if t = f(t1, . . . , tn) , then σ̂[t] = σ(f)(σ̂[t1], . . . , σ̂[tn]), where f is an n-ary operation symbol and t1,. . . , tn are terms. The set Hyp(τ) is a monoid. Let M be a submonoid of Hyp(τ). An algebra A is said to M - hypersatisfy an identity t ≈ s if for every hypersubstitution σ ∈ M , the identity σ̂[t] ≈ σ̂[s] holds in A. A variety V is called M -solid if every identity of V is M -hypersatisfied in V . The closure operator is defined on the set of identities of a given type τ as follows: χM [u ≈ v] := {σ̂[u] ≈ σ̂[v] \| σ ∈ M} and χM [Σ] =⋃ u≈v∈Σ χM [u ≈ v]. Given an algebra A = 〈A;FA〉 and a hypersubstitution σ, then σ[A] = 〈A; (σ(FA)〉 := 〈A; (σ(f)A)f∈F 〉 is called the derived algebra. The closure operator ψM on the set of algebras of a given type τ , is de- fined as follows: ψM [A] = {σ[A] \| σ ∈M} and ψM [R] = ⋃ A∈R ψM [A]. It is well known [5] that if M is a monoid of hypersubstitutions of type τ , then the class of all M -solid varieties of type τ forms a complete sublattice of the lattice L(τ) of all varieties of type τ . Our aim is to transfer these results to another kind of hypersubstitu- tion and to coloured terms. In Section 1 we present two constructions which produce composed terms. The first one is inductive and the resulting term is obtained by simultaneous replacement of a subterm in all places where it occurs in a Jo u rn al A lg eb ra D is cr et e M at h .Sl. Shtrakov 115 given term with another term of the same type. The positional composi- tion gives a composed term as a result of the replacement of subterms in given positions with other terms of the same type. The positional com- position of colored terms is an associative operation. In [4] the authors studied colored terms which are supplied with one coloration. This is a very “static" concept where each term has one fixed coloration. Here we consider composition of terms which produces an image of terms and coloration of this image. This “dynamical" point of view gives us an advantage when studying multi-hypersubstitutions, multi-solid varieties etc. In Section 2 we use colored terms to investigate the monoid of multi- hypersubstitutions. It is proved that the lattice of multi-solid varieties is a sublattice of the lattice of solid varieties. A series of assertions are proved, which characterize multi-solid varieties and the corresponding closure op- erators. We study multi-solid varieties by deduction of a fully invariant congruence. The completeness theorem for multi-hyperequational theo- ries is proved. A tree automata realization of multi-hypersubstitutions is given in Section 3. 1. Composition of colored terms The concept of the composition of mappings is fundamental in almost all mathematical theories. Usually we consider composition as an oper- ation which inductively replaces some variables with other objects such as functions, terms, etc. Here, we consider a more general case when the replacement can be applied to objects which may be variables or sub- functions, subterms, etc. which are located at a given set of positions. If t is a term, then the set var(t) consisting of these elements of X which occur in t is called the set of input variables (or variables) for t. If t = f(t1, . . . , tn) is a non-variable term, then f is root symbol (root) of t and we will write f = root(t). For a term t ∈ Wτ (X) the set Sub(t) of its subterms is defined as follows: if t ∈ X ∪ F0, then Sub(t) = {t} and if t = f(t1, . . . , tn), then Sub(t) = {t} ∪ Sub(t1) ∪ . . . ∪ Sub(tn). The depth of a term t is defined inductively: if t ∈ X ∪ F0 then Depth(t) = 0; and if t = f(t1, . . . , tn), then Depth(t) = max{Depth(t1), . . . , Depth(tn)}+ 1. Definition 1. Let r, s, t ∈ Wτ (X) be three terms of type τ . By t(r ← s) we will denote the term, obtained by simultaneous replacement of every occurrence of r as a subterm of t by s. This term is called the inductive Jo u rn al A lg eb ra D is cr et e M at h .116 Multi-Solid Varieties and Mh-transducers composition of the terms t and s, by r. I.e. (i) t(r ← s) = t if r /∈ Sub(t); (ii) t(r ← s) = s if t = r and (iii) t(r ← s) = f(t1(r ← s), . . . , tn(r ← s)), if t = f(t1, . . . , tn) and r ∈ Sub(t), r 6= t. If ri /∈ Sub(rj) when i 6= j, then t(r1 ← s1, . . . , rm ← sm) means the inductive composition of t, r1, . . . , rm, s1, . . . , sm. In the particular case when rj = xj for j = 1, . . . ,m and var(t) = {x1, . . . , xm} we will briefly write t(s1, . . . , sm) instead of t(x1 ← s1, . . . , xm ← sm). Let τ be a type and F be its set of operation symbols. Denote by maxar = max{τ(f)\|f ∈ F} and INF := {m ∈ IN \| m ≤ maxar}. Let IN∗ F be the set of all finite strings over INF . The set IN∗ F is naturally ordered by p � q ⇐⇒ p is a prefix of q. The Greek letter ε, as usual denotes the empty word (string) over INF . For any term t, the set of positions Pos(t) ⊆ IN∗ F of t is induc- tively defined as follows: Pos(t) = {ε} if t ∈ X ∪ F0 and Pos(t) := {ε} ⋃ 1≤i≤n(iPos(ti)), if t = f(t1, . . . , tn), n ≥ 0, where iPos(ti) := {iq\|q ∈ Pos(ti)}, and iq is concatenation of the strings i and q from IN∗ F . For a given position p ∈ Pos(t), the length of p is denoted by l(p). Any term can be regarded as a tree with nodes labelled with the operation symbols and its leaves labelled as variables or nullary operation symbols. Let t ∈ Wτ (X) be a term of type τ and let subt : Pos(t) → Sub(t) be the function which maps each position in a term t to the subterm of t, whose root node occurs at that position. Definition 2. Let t, r ∈ Wτ (X) be two terms of type τ and p ∈ Pos(t) be a position in t. The positional composition of t and r on p is a term s := t(p; r) obtained from t when replacing the term subt(p) by r on the position p, only. More generally, the positional composition of terms is naturally de- fined for the compositional pairs t(p1, . . . , pm; t1, . . . , tm), also. Remark 1. The positional composition has the following properties: 1. If 〈〈p1, p2〉, 〈t1, t2〉〉 is a compositional pair of t, then t(p1, p2; t1, t2) = t(p1; t1)(p2; t2) = t(p2; t2)(p1; t1); 2. If S = 〈p1, . . . , pm〉 and T = 〈t1, . . . , tm〉 with (∀pi, pj ∈ S) (i 6= j =⇒ pi 6≺ pj & pj 6≺ pi) Jo u rn al A lg eb ra D is cr et e M at h .Sl. Shtrakov 117 and π is a permutation of the set {1, . . . ,m}, then t(p1, . . . , pm; t1, . . . , tm) = t(pπ(1), . . . , pπ(m); tπ(1), . . . , tπ(m)). 3.If t, s, r ∈ Wτ (X), p ∈ Pos(t) and q ∈ Pos(s), then t(p; s(q; r)) = t(p; s)(pq; r). We will denote respectively “← ” for inductive composition and “; ” for positional composition. The concept of colored terms is important when studying deductive closure of sets of identities and the lattice of varieties of a given type. Col- ored terms (trees) are useful tools in Computer Science, General Algebra, Theory of Formal Languages, Programming, Automata theory etc. Let t be a term of type τ. Let us denote by SubF (t) the set of all subterms of t which are not variables, i.e. whose roots are labelled by an operation symbol from F and let PosF (t) := {p ∈ Pos(t) \| subt(p) ∈ SubF (t)}. Any function αt : PosF (t) → IN is called a coloration of the term t. For a given term t, PosX(t) denotes the set of all its variable positions i.e. PosX(t) := Pos(t) \ PosF (t). By Ct we denote the set of all colorations of the term t i.e. Ct := {αt \| αt : PosF (t) → IN}. If p ∈ PosF (t) then αt(p) ∈ IN denotes the value of the function αt which is associated with the root operation sym- bol of the subterm s = subt(p), and αt[p] ∈ Cs denotes the "restriction" of the function αt on the set PosF (s) defined by αt[p](q) = αt(pq) for all q ∈ PosF (s). Definition 3. The set W c τ (X) of all colored terms of type τ is defined as follows: (i) X ⊂W c τ (X); (ii) If f ∈ F , then 〈f, q〉 ∈W c τ (X) for each q ∈ IN; (iii) If t = f(t1, . . . , tn) ∈ Wτ (X), then 〈t, αt〉 ∈ W c τ (X) for each αt ∈ Ct. Let 〈t, αt〉 ∈ W c τ (X). The set Subc(〈t, αt〉) of colored subterms of 〈t, αt〉 is defined as follows: For x ∈ X we have Subc(x) := {x} and if 〈t, αt〉 = 〈f, q〉(〈t1, αt1〉, . . . , 〈tn, αtn〉), then Subc(〈t, αt〉) := {〈t, αt〉} ∪ Subc(〈t1, αt1〉) ∪ . . . ∪ Subc(〈tn, αtn〉). Let 〈t, αt〉, 〈r, αr〉 and 〈s, αs〉 be colored terms of type τ . Their in- ductive composition 〈t, αt〉(〈r, αr〉 ← 〈s, αs〉) is defined as follows: Jo u rn al A lg eb ra D is cr et e M at h .118 Multi-Solid Varieties and Mh-transducers (i) if t = xi ∈ X, then xi(〈r, αr〉 ← 〈s, αs〉) := { 〈s, αs〉 if r = xi; xi otherwise (ii) if t = f(t1, t2, . . . , tn), αt(ε) = q, αt[i] = αti for i = 1, 2, . . . , n, then 〈t, αt〉(〈r, αr〉 ← 〈s, αs〉) := 〈s, αs〉 when 〈r, αr〉 = 〈t, αt〉 and 〈t, αt〉(〈r, αr〉 ← 〈s, αs〉) := 〈f, q〉(〈t1, αt1〉(〈r, αr〉 ← 〈s, αs〉), . . . , 〈tn, αtn〉(〈r, αr〉 ← 〈s, αs〉) otherwise. If 〈ri, αri 〉 /∈ Subc(〈rj , αrj 〉) for i 6= j, then the denotations 〈t, αt〉(〈r1, αr1 〉 ← 〈s1, αs1 〉, . . . , 〈rm, αrm〉 ← 〈sm, αsm〉) is clear. Let 〈t, αt〉, 〈s, αs〉 ∈ W c τ (X) be two colored terms of type τ and let p ∈ Pos(t). The positional composition of the colored terms 〈t, αt〉 and 〈s, αs〉 at the position p is defined as follows: 〈t, αt〉(p; 〈s, αs〉) := 〈t(p; s), α〉, where α(q) = { αs(k) if q = pk, for some k ∈ Pos(s); αt(q) otherwise. The positional composition of colored terms can be defined for a se- quence (p1, . . . , pm) ∈ Pos(t)m of positions with (∀pi, pj ∈ S) (i 6= j =⇒ pi 6≺ pj & pj 6≺ pi). It is denoted by 〈t, αt〉(p1, . . . , pm; 〈s1, αs1 〉, . . . , 〈sm, αsm〉). Theorem 1. If t, s, r ∈Wτ (X), p ∈ Pos(t) and q ∈ Pos(s), then 〈t, αt〉(p; 〈s, αs〉(q; 〈r, αr〉)) = 〈t, αt〉(p; 〈s, αs〉)(pq; 〈r, αr〉), where αt ∈ Ct, αs ∈ Cs, αr ∈ Cr. Proof. Let us consider the non-trivial case when t, r and s are not vari- ables. Thus we obtain 〈s, αs〉(q; 〈r, αr〉) = 〈s(q; r), α〉, where α(m) = { αr(k) if m = qk, for some k ∈ PosF (r); αs(m) otherwise and 〈t, αt〉(p; 〈s(q; r), α〉) = 〈t(p; s(q; r)), β〉, where β(l) = { α(v) if l = pv, for some v ∈ PosF (s(q; r)); αt(l) otherwise = Jo u rn al A lg eb ra D is cr et e M at h .Sl. Shtrakov 119 =    αr(k) if l = pqk, for some k ∈ PosF (r); αs(v) if l = pv, for some v ∈ PosF (s), q 6≺ v; αt(l) otherwise. On the other side we obtain 〈t, αt〉(p; 〈s, αs〉) = 〈t(p; s), γ〉, where γ(m) = { αs(v) if m = pv, for some v ∈ PosF (s); αt(m) otherwise and 〈t(p; s), γ〉 = 〈t(p; s)(pq; r), δ〉, where δ(l) = { αr(k) if l = pqk, for some k ∈ PosF (r); γ(l) otherwise = =    αr(k) if l = pqk, for some k ∈ PosF (r); αs(v) if l = pv, for some v ∈ PosF (s), q 6≺ v; αt(l) otherwise. Clearly, δ = β and t(p; s(q; r)) = t(p; s)(pq; r). The following example illustrates the positions, subterms and posi- tional composition of colored terms. Example 1. Let τ = (2), F = {f}. The colorations of terms in the example are presented as bold superscripts of the operation symbols. Let 〈t, αt〉 = f1(f1(x1, x2), f 2(x1, x2)), 〈s, αs〉 = f3(f2(x1, x2), x2) and 〈r, αr〉 = f3(x1, x2) be three colored terms of type τ . Then we have Pos(t) = {ε, 1, 2, 11, 12, 21, 22}, 〈subt(2), αt[2]〉 = f2(x1, x2), 〈subt(12), αt[12]〉 = x2 and Subc(〈s, αs〉) = {〈s, αs〉, 〈f(x1, x2), αs[1]〉, x1, x2}. For the positional composition we have 〈t, αt〉(2; 〈s, αs〉(12; 〈r, αr〉)) = f1(f1(x1, x2), f 3(f2(x1, x2), x2))(212; 〈r, αr〉) = f1(f1(x1, x2), f 3(f2(x1, f 3(x1, x2)), x2)) = 〈t, αt〉(2; 〈s, αs〉)(212; 〈r, αr〉). 2. Multi-hypersubstitutions and deduction of identities Definition 4. [4] Let M be a submonoid of Hyp(τ) and let ρ be a mapping of IN into M i.e. ρ : IN → M. Any such mapping is called a multi-hypersubstitution of type τ over M . Denote by σq the image of q ∈ IN under ρ i.e. ρ(q) = σq ∈ Hyp(τ). Let σ ∈M and ρ ∈Mhyp(τ,M). If there is a natural number q ∈ IN with ρ(q) = σ, then we will write σ ∈ ρ. Jo u rn al A lg eb ra D is cr et e M at h .120 Multi-Solid Varieties and Mh-transducers @ @ @ @@I � � �� @ @ @I r r r r � � �� @ @ @I r r r 1 1 x1 x2 x1 x2 2 〈t, αt〉 @ @ @ @@I � � �� @ @ @I r r r r � � �� @ @ @I r r r 1 2 x2 x2 1 ρ[〈t, αt〉] � � �� @ @ @I r r r x2 x1 x1 2 Figure 1: Multi-hypersubstitution of colored terms We will define the extension ραt of a multi-hypersubstitution ρ to the set of colored subterms of a term. Let 〈t, αt〉 be a colored term of type τ , αt ∈ Ct, with p ∈ Pos(t), s = subt(p) and αt(p) = m. Then we set: (i) if s = xj ∈ X, then ραt [s] := xj ; (ii) if s = f(s1, . . . , sn), then ραt [s] := σm(f)(ραt [s1], . . . , ραt [sn]). The extension of ρ on αs assigns inductively a coloration ρt[αs] to the term ραt [s], as follows: (i) if s = f(x1, . . . , xn), then ρt[αs](q) := m for all q ∈ PosF (ραt [s]); (ii) if s = f(s1, . . . , sn), and q ∈ PosF (ραt [s]), then ρt[αs](q) =    m if q ∈ PosF (σm(f)); ρt[αsj ](k) if q = lk, for some j, j ≤ n, k ∈ PosF (ραt [sj ]), l ∈ Pos X(σm(f)). Definition 5. The mapping ρ on the set W c τ (X) is defined as follows: (i) ρ[x] := x for all x ∈ X; (ii) if t = f(t1, . . . , tn) and αt ∈ Ct, then ρ[〈t, αt〉] := 〈ραt [t], ρt[αt]〉. Example 2. Let 〈t, αt〉 and 〈s, αs〉 be the colored terms of type τ from Example 1. Let σ1(f) = f(x2, x1), σ2(f) = f(f(x2, x1), x2) and σ3(f) = f(x1, x2) be hypersubstitutions of type τ and M = {σ1, σ2, σ3, . . .} be a submonoid of Hyp(τ). Let ρ ∈Mhyp(τ,M) with ρ(m) := σm. Then we obtain ρ[〈t, αt〉] = ρ[f1(f1(x1, x2), f 2(x1, x2))] = f1(f2(f2(x2, x1), x2), f 1(x2, x1)) and ρ[〈s, αs〉] = ρ[f3(f2(x1, x2), x2)] = f3(f2(f2(x2, x1), x2), x2). The image of 〈t, αt〉 under ρ is shown in Figure 1. Jo u rn al A lg eb ra D is cr et e M at h .Sl. Shtrakov 121 Proposition 1. Let ρ ∈ Mhyp(τ,M) be a multi-hypersubstitution and t, s ∈Wτ (Xn) with αt ∈ Ct, αs ∈ Cs and p ∈ Pos(t) . Then ρ[〈t, αt〉(p; 〈s, αs〉)] = ρ[〈t, αt〉(p;xj)](xj ← ρ[〈s, αs〉]), for each j, j > n. Proof. We will use induction on the length l(p) of the position p. First, let us observe that the case l(p) = 0 is trivial. So, our basis of induction is l(p) = 1. Then t = f(t1, . . . , tp−1, tp, tp+1, . . . , tm) for some f ∈ Fm. Hence, for each j, j > n, we have ρ[〈t, αt〉(p; 〈s, αs〉)] = ρ[〈f(t1, . . . , tp−1, s, tp+1, . . . , tm), αt′〉] = = ρ[〈f(t1, . . . , tp−1, xj , tp+1, . . . , tm)(xj ← s), αt′〉] = = ρ[〈t, αt〉(p;xj)](xj ← ρ[〈s, αs〉]), where αt′ is a coloration of the term t′ = f(t1, . . . , tp−1, s, tp+1, . . . , tm) for which αt′(q) = αt(q) when q ∈ PosF (t) \ {p} and αt′(pq) = αs(q) when q ∈ PosF (s). Our inductive supposition is that when l(p) < k, the proposition is true, for some k ∈ IN. Let l(p) = k and p = qi where q ∈ IN∗ F and i ∈ IN. Hence q ∈ PosF (t) and l(q) < k. Let u, v ∈ Sub(t) be subterms of t for which u = subt(p) and v = subt(q). Then we have v = g(v1, . . . , vi−1, vi, vi+1, . . . , vj) with vi = u for some g ∈ Fj . By the inductive supposition, for every j, j > n and l, l > n, we obtain ρ[〈t, αt〉(p; 〈s, αs〉)] = = ρ[〈t, αt〉(q;xj)(xj ← ρ[〈v, αt[q]〉(i; 〈s, αs〉)] = = ρ[〈t, αt〉(qi;xl)](xl ← ρ[〈s, αs〉]) = ρ[〈t, αt〉(p;xj)](xj ← ρ[〈s, αs〉]). A binary operation is defined in the set Mhyp(τ,M) as follows: Definition 6. Let ρ(1) and ρ(2) be two multi-hypersubstitutions over the submonoid M . Then the composition ρ(1) ◦ch ρ (2) : IN → M maps each color q ∈ IN as follows: (ρ(1) ◦ch ρ (2))(q) := ρ(1)(q) ◦h ρ (2)(q) := σ(1) q ◦h σ (2) q . Lemma 1. For every two multi-hypersubstitutions ρ(1) and ρ(2) over M and for each colored term 〈t, αt〉 of type τ , it holds (ρ(1) ◦ch ρ(2))[〈t, αt〉] = ρ(1)[ρ(2)[〈t, αt〉]]. Jo u rn al A lg eb ra D is cr et e M at h .122 Multi-Solid Varieties and Mh-transducers So, Mhyp(τ,M) is a monoid, where ρid = (σid, σid, . . .) is the identity multi-hypersubstitution. Let A = 〈A,F〉 be an algebra of type τ. Each colored term 〈t, αt〉 defines a term-operation on the set A, as follows 〈t, αt〉 A = tA. Let ρ = (σ1, σ2, . . .) be any multi-hypersubstitution over a monoid M of hypersubstitutions of type τ , and let ρ(F) = {t ∈Wτ (X) \| ∃ σ ∈ ρ and f ∈ F such that t = σ(f)}. The algebra ρ[A] := 〈A, ρ(F)ρ[A]〉 is called a derived algebra under the multi-hypersubstitution ρ. Let R be a class of algebras of type τ . The operator ψc M is defined as follows: ψc M [A] := {ρ[A] \| ρ ∈Mhyp(τ,M)} and ψc M [R] := {ψc M [A] \| A ∈ R}. Lemma 2. For each 〈t, αt〉 ∈W c τ (X) it holds 〈t, αt〉 ρ[A] = ρ[〈t, αt〉] A. Proof. If t = xj ∈ X, then ρ[〈t, αt〉] A = xAj and 〈t, αt〉 ρ[A] = x ρ[A] j = xAj . Let us assume that t = f(t1, . . . , tn), αt(ε) = q ∈ IN, 〈f, q〉ρ[A] = ρ(〈f, q〉)A and 〈ti, αti〉 ρ[A] = ρ[〈ti, αti〉] A for all i = 1, . . . , n, then we have 〈t, αt〉 ρ[A] = 〈f, q〉ρ[A](〈t1, αt[1]〉ρ[A], . . . , 〈tn, αt[n]〉ρ[A]) = = ρ(〈f, q〉)A(ρ[〈t1, αt[1]〉]A, . . . , ρ[〈tn, αt[n]〉]A) = ρ[〈t, αt〉] A. Let ρ be a multi-hypersubstitution. By ρ[t ≈ s] we will denote ρ[t ≈ s] := {ραt [t] ≈ ραs [s] \| αt ∈ Ct, αs ∈ Cs}. Let Σ ⊆ Id(τ) be a set of identities of type τ . The operator χc M , is defined as follows: χc M [t ≈ s] := {ρ[t ≈ s] \| ρ ∈Mhyp(τ,M)} and χc M [Σ] := {χc M [t ≈ s] \| t ≈ s ∈ Σ}. Definition 7. An identity t ≈ s ∈ IdA in the algebra A is called an M -multi-hyperidentity in A, if for each multi-hypersubstitution ρ ∈ Mhyp(τ,M) and for every two colorations αt ∈ Ct, αs ∈ Cs, the iden- tity ραt [t] ≈ ραs [s] is satisfied in A. When t ≈ s is an M -multi- hyperidentity in A we will write A \|=Mh t ≈ s, and the set of all M -multi-hyperidentities in A is denoted by HCMIdA. Algebras in which all identities are M -multi-hyperidentities are called M -multi-solid i.e. an algebra A of type τ is M -multi-solid, if χc M [IdA] ⊆ IdA. So, if V ⊆ Alg(τ) is a variety of type τ , it is called M -multi-solid, when χc M [IdV ] ⊆ IdV. Jo u rn al A lg eb ra D is cr et e M at h .Sl. Shtrakov 123 Theorem 2. Let Σ ⊆ Id(τ) and R ⊆ Alg(τ). Then (i) χM [Σ] ⊆ χc M [Σ] for all Σ ⊆ Id(τ); (ii) ψM [R] = ψc M [R] for all R ⊆ Alg(τ). Proof. (i) Let σ ∈ M . Then we consider the multi-hypersubstitution ρ ∈ Mhyp(τ,M) with ρ(q) = σ for all q ∈ IN. If t ∈ Wτ (X) then we will show that σ̂[t] = ραt [t] for αt ∈ Ct. We will prove more, that σ̂[r] := ραr [r] for each r ∈ Sub(t). That will be proved by induction on the depth of the term r. If r ∈ X then σ̂[r] = ραt [r] = r. Let us assume that r = f(r1, . . . , rn) with r1, . . . , rn ∈ Sub(t). Our inductive supposition is that σ̂[rk] = ραt [rk] for 1 ≤ k ≤ n. Then we have ραt [r] = ρ(αt(ε))(f)(ραt [r1], . . . , ραt [rn]) = σ(f)(σ̂[r1], . . . , σ̂[rn]) = = σ̂[f(r1, . . . , rn)] = σ̂[r]. Let t ≈ s ∈ Σ. Thus we have σ̂[t] = ραt [t], σ̂[s] = ραs [s] and σ̂[t] ≈ σ̂[s] ∈ χM [Σ] ⇐⇒ ραt [t] ≈ ραs [s] ∈ χc M [Σ]. Hence σ̂[t] ≈ σ̂[s] ∈ χc M [Σ]. (ii) Let A ∈ R and q ∈ IN be the color of f in the fundamental colored term 〈f(x1, . . . , xn), q〉. Let ρ ∈ Mhyp(τ,M). Then we consider the hypersubstitution σ ∈M with σ(f) = ρ(q)(f) and from Lemma 2 we obtain 〈f, q〉ρ[A] = ρ[〈f(x1, . . . , xn), q〉]A = (ρ(q)(f)(x1, . . . , xn))A = σ(f)(x1, . . . , xn)A. This shows that ψc M [A] ⊆ ψM [A]. Let σ ∈ Hyp(τ), A ∈ R and ρ ∈ Mhyp(τ,M) with ρ(q) = σ for all q ∈ IN. From Lemma 2 we obtain σ(f)A = σ̂[f(x1, . . . , xn)]A = ρ[〈f(x1, . . . , xn), q〉]A = = 〈f(x1, . . . , xn), q〉]ρ[A] = 〈f, q〉ρ[A]. This shows that ψM [A] ⊆ ψc M [A]. Altogether we have ψc M [A] = ψM [A] and thus ψc M [R] = ψM [R]. Theorem 3. Each M -multi-solid variety is M -solid, but the converse assumption is in general not true i.e. there are M−solid varieties which are not M−multi-solid. Jo u rn al A lg eb ra D is cr et e M at h .124 Multi-Solid Varieties and Mh-transducers Proof. Let V be an M -multi-solid variety. If t ≈ s ∈ χM [IdV ], then t ≈ s ∈ χc M [IdV ] because of (i) of Theorem 2. Hence every M -multi- solid variety is M -solid one. Let RB be the variety of rectangular bands, which is of type τ = (2). The identities satisfied in RB are: IdRB = {f(x1, f(x2, x3)) ≈ f(f(x1, x2), x3) ≈ f(x1, x3), f(x1, x1) ≈ x1}. In [5] it was proved that RB is a solid variety, which means that for each identity t ≈ s with IdRB \|= t ≈ s and for each hypersubstitution σ we have IdRB \|= σ̂[t] ≈ σ̂[s]. Let M , ρ , 〈t, αt〉 and 〈s, αs〉 be as in Example 2 i.e. 〈t, αt〉 = f1(f1(x1, x2), f 2(x1, x2)) and 〈s, αs〉 = f3(f2(x1, x2), x2). Since t = f(f(x1, x2), f(x1, x2)) ≈ f(x1, x2) ≈ f(x1, f(x2, x2)) ≈ f(f(x1, x2), x2), it follows that IdRB \|= t ≈ s. Following the results in Example 2 we have ραt [t] = f(f(f(x2, x1), x2), f(x2, x1)) and ραs [s] = f(f(f(x2, x1), x2), x2). Thus we obtain IdRB \|= ραt [t] ≈ f(x2, x1) and IdRB \|= ραs [s] ≈ x2. Hence IdRB 6\|= ραt [t] ≈ ραs [s], and RB is not M -multi-solid. The operators χc M and ψc M are connected by the condition that ψc M [A] satisfies u ≈ v ⇐⇒ A satisfies χc M [u ≈ v]. ψc M and χc M are additive and closure operators. Let R ⊂ Alg(τ) and Σ ⊂ Id(τ). Then we set: HCMModΣ := {A ∈ Alg(τ) \| t ≈ s ∈ Σ =⇒ A \|=Mh t ≈ s}; HCMIdR := {t ≈ s ∈ Id(τ) \| χc M [t ≈ s] ⊆ IdR}; and HCMV arR := HCMModHCMIdR. A set Σ of identities of type τ is called anM−multi-hyperequational theory if Σ = HCMIdHCMModΣ and a class R of algebras of type τ is called an M−multi-hyperequational class if R = HCMModHCMIdR. Theorem 4. Let Σ ⊆ Id(τ) and R ⊆ Alg(τ). If Σ = HCMIdR and R = HCMModΣ, then R = ModΣ and Σ = IdR. Proof. Let Σ = HCMIdR and R = HCMModΣ. First, we will prove that Σ = χc M [Σ] and R = ψc M [R]. χc M and ψc M are closure operators and hence we have Σ ⊆ χc M [Σ] and R ⊆ ψc M [R]. We will prove the converse inclusions. Let r ≈ v ∈ χc M [Σ]. Then there is an identity t ≈ s ∈ Σ with r ≈ v ∈ χc M [t ≈ s], i.e. χc M [r ≈ v] ⊆ χc M [χc M [t ≈ s]] ⊆ χc M [t ≈ s]. From t ≈ s ∈ Σ it follows t ≈ s ∈ HCMIdR, Jo u rn al A lg eb ra D is cr et e M at h .Sl. Shtrakov 125 χc M [t ≈ s] ⊆ IdR and χc M [r ≈ v] ⊆ χc M [t ≈ s] ⊆ IdR. Hence r ≈ v ∈ HCMIdR and r ≈ v ∈ Σ, i.e. Σ = χc M [Σ]. Let A ∈ ψc M [R]. Then there is an algebra B ∈ R with A ∈ ψc M [B], i.e. A = ρ[B] for some ρ ∈Mhyp(τ,M). Hence ψc M [A] = ψc M [ρ[B]] ⊆ ψc M [B]. Since B ∈ R = HCMModΣ we have χc M [Σ] ⊆ IdB i.e. ψc M [B] ⊆ ModΣ and ψc M [A] ⊆ ψc M [B] ⊆ ModΣ. Hence A ∈ HCMModΣ and A ∈ R, i.e. R = ψc M [R]. Now, we obtain ModΣ = {A \| Σ ⊆ IdA} = {A \| χc M [Σ] ⊆ IdA} = HCMModΣ = R and IdR = {r ≈ v \| R \|= r ≈ v} = {r ≈ v \| ψc M [R] \|= r ≈ v} = HCMIdR = Σ. Hence R = ModΣ and Σ = IdR. Proposition 2. Let A ∈ Alg(τ), R ⊆ Alg(τ), t ≈ s ∈ Id(τ), Σ ⊆ Id(τ), αt ∈ Ct and αs ∈ Cs and let ρ be a multi-hypersubstitution over M . Then we have: (i) A \|= ραt [t] ≈ ραs [s] ⇐⇒ ρ[A] \|= t ≈ s ; (ii) A \|=Mh t ≈ s ⇐⇒ χc M [t ≈ s] ⊆ IdA ⇐⇒ ψc M [A] \|= t ≈ s; (iii) Σ ⊆ HCMIdR ⇐⇒ χc M [Σ] ⊆ IdR ⇐⇒ Σ ⊆ Idψc M [R] (iv) R ⊆ HCMModΣ ⇐⇒ ψc M [R] ⊆ModΣ ⇐⇒ R ⊆Modχc M [Σ] (v) HCMIdR ⊆ IdR; (vi) V arR ⊆ HCMV arR; (vii) The pair 〈HCMId,HCMMod〉 forms a Galois connection. Proof. (i) follows from Theorem 4 and Lemma 2. (ii) Let ρ be an arbitrary multi-hypersubstitution over the monoid M . Let us assume that A \|=Mh t ≈ s. Hence A \|= ραt [t] ≈ ραs [s] i.e. A \|= χc M [t ≈ s] and ψc M [A] \|= t ≈ s. (iii) and (v) follow from (ii). (iv) follows from (iii). (vi) From (ii), it follows that HCMV arR is a variety. Then R ⊆ HCMV arR, and V arR ⊆ HCMV arR. (vii) follows from Theorem 4. Proposition 3. For every Σ ⊆ Id(τ) and R ⊆ Alg(τ) the following hold: (i) χc M [HCMIdR] = HCMIdR = Idψc M [R]; (ii) ψc M [HCMModΣ] = HCMModΣ = Modχc M [Σ]; (iii) V arψc M [R] = HCMV arR = ModHCMIdR; (iv) Modχc M [Σ] = HCMModΣ = IdHCMModΣ; (iv) Idψc M [R] = HCMIdR = ModHCMIdR. Proof. (i) From Proposition 2 we obtain HCMIdR ⊆ HCMIdR =⇒ χc M [χc M [HCMIdR]] ⊆ χc M [HCMIdR] ⊆ IdR =⇒ χc M [HCMIdR] ⊆ HCMIdR. Jo u rn al A lg eb ra D is cr et e M at h .126 Multi-Solid Varieties and Mh-transducers The converse inclusion is obvious. (ii) can be proved in an analogous way as (i). (iii) We have consequently, HCMV arR = HCMModHCMIdR = Modχc M [HCMIdR] = ModHCMIdR = ModIdψc M [R] = V arψc M [R]. (iv) and (v) can be proved in an analogous way as (iii). For given set Σ of identities the set IdModΣ of all identities satisfied in the variety ModΣ is the deductive closure of Σ, which is the smallest fully invariant congruence containing Σ (see [1, 2, 9]). A remarkable fact is, that there exists a variety V ⊂ Alg(τ) with IdV = Σ if and only if Σ is a fully invariant congruence [2]. A congruence Σ ⊆ Id(τ) is called a fully invariant congruence if it additionally satisfies the following axioms (some authors call them “de- ductive rules", “derivation rules", “productions" etc.): (i) (variable inductive substitution) (t ≈ s ∈ Σ) & (r ∈ Wτ (X)) & (x ∈ var(t)) =⇒ t(x ← r) ≈ s(x ← r) ∈ Σ; (ii) (term positional replacement) (t ≈ s ∈ Σ) & (r ∈Wτ (X)) & (subr(p) = t) =⇒ r(p; s) ≈ r ∈ Σ. For any set of identities Σ the smallest fully invariant congruence containing Σ is called the D−closure of Σ and it is denoted by D(Σ). In [5] totally invariant congruences are studied as fully invariant con- gruences which preserve the hypersubstitution images i.e. if t ≈ s ∈ Σ then σ̂[t] ≈ σ̂[s] ∈ Σ for all σ ∈ Hyp(τ). We extend that results, to the case of multi-hypersubstitutions over a given submonoid M ⊆ Hyp(τ). Definition 8. A fully invariant congruence Σ is Mh-deductively closed if it additionally satisfies Mh1 (Multi-Hypersubstitution) (t ≈ s ∈ Σ) & (ρ ∈Mhyp(τ,M)) =⇒ ρ[t ≈ s] ⊆ Σ. For any set of identities Σ the smallest Mh−deductively closed set containing Σ is called the Mh−closure of Σ and it is denoted by Mh(Σ). It is clear that for each fully invariant congruence Σ we have Mh(Σ) = χc M [Σ]. Let Σ be a set of identities of type τ. For t ≈ s ∈ Id(τ) we say Σ ⊢Mh t ≈ s (“Σ Mh-proves t ≈ s") if there is a sequence of identities t1 ≈ s1, . . . , tn ≈ sn, such that each identity belongs to Σ or is a result of Jo u rn al A lg eb ra D is cr et e M at h .Sl. Shtrakov 127 applying any of the derivation rules of fully invariant congruence or Mh1- rule to previous identities in the sequence and the last identity tn ≈ sn is t ≈ s. Let t ≈ s be an identity and A be an algebra of type τ . Then A \|=Mh t ≈ s means that A \|= Mh(t ≈ s) (see Definition 7). Let Σ ⊆ Id(τ) be a set of identities and A be an algebra of type τ . Then A \|=Mh Σ means that A \|= Mh(Σ). For t, s ∈ Wτ (X) we say Σ \|=Mh t ≈ s (read: “Σ Mh−yields t ≈ s") if, given any algebra B ∈ Alg(τ), B \|=Mh Σ ⇒ B \|=Mh t ≈ s. Remark 2. In a more general case we have χc M [Σ] ⊆ Mh(Σ) and there are examples when χc M [Σ] 6= Mh(Σ). It is easy to see that each Mh−deductively closed set is a totally invariant congruence [5]. On the other side from Theorem 3 it follows that the totally invariant congruence IdRB is not Mh−deductively closed. Lemma 3. For any set Σ ⊆ Id(τ) of identities and t ≈ s ∈ Id(τ) the following equivalences hold: Σ ⊢Mh t ≈ s ⇐⇒ χc M [Σ] ⊢ t ≈ s ⇐⇒ Mh(Σ) ⊢ t ≈ s. Theorem 5. (Completeness Theorem for Multi-hyperequational Logic.) For Σ ⊆ Id(τ) and t ≈ s ∈ Id(τ) we have: Σ \|=Mh t ≈ s ⇐⇒ Σ ⊢Mh t ≈ s. Proof. From HCMIdHCMModΣ = IdHCMModΣ = IdModχc M [Σ] we obtain that Σ \|=Mh t ≈ s is equivalent to t ≈ s ∈ HCMIdHCMModΣ. From Theorem 14.19 [2] we have HCMIdHCMModΣ \|= t ≈ s and HCMIdHCMModΣ ⊢ t ≈ s. Hence χc M [Σ] ⊢ t ≈ s and Σ ⊢Mh t ≈ s. The converse implication follows from the fact that Mh(Σ) is a fully invariant congruence which is closed under the rule Mh1. Corollary 1. Let M be a submonoid of Hyp(τ). Then the class of all M−multi-solid varieties of type τ is a complete sublattice of the lattice L(τ) of all varieties of type τ and dually, the class of all M−multi- hyperequational theories of type τ is a complete sublattice of the lattice E(τ) of all equational theories (fully invariant congruences) of type τ . Lemma 4. For any set Σ ⊆ Id(τ) of identities and t ≈ s ∈ Id(τ) the following equivalence holds: Σ \|=Mh t ≈ s ⇐⇒ Mh(Σ) \|= t ≈ s. Jo u rn al A lg eb ra D is cr et e M at h .128 Multi-Solid Varieties and Mh-transducers Proof. “ ⇒ ” Let Σ \|=Mh t ≈ s. We have to prove Mh(Σ) \|= t ≈ s. Let A ∈ Alg(τ) be an algebra for which A \|= Mh(Σ). This implies A \|=Mh Σ and A \|=Mh t ≈ s, because of Σ \|=Mh t ≈ s. Hence A \|= Mh(t ≈ s). On the other side, we have t ≈ s ∈Mh(t ≈ s) and A \|= t ≈ s. “ ⇐ ” Let Mh(Σ) \|= t ≈ s. Since χc M [Σ] ⊆ Mh(Σ) and from Propo- sition 2 (ii) we have Σ \|=Mh t ≈ s. Corollary 2. For any set Σ ⊆ Id(τ) of identities and t ≈ s ∈ Id(τ) it holds: Σ \|=Mh t ≈ s ⇐⇒ χc M [Σ] \|= t ≈ s. Example 3. Let τ be an arbitrary type. (i) Let t ∈ Wτ (X) be a term of type τ. Let us consider the following two functions Left : Wτ (X)→ X and Right : Wτ (X)→ X, which assign to each term t the leftmost and the rightmost variable of t. For instance, if t = g(f(x1, x2), x3, x4), then Left(t) = x1 and Right(t) = x4. Let us denote by K1 ⊂ Hyp(τ) the set of all hypersubstitutions which preserve the functions Left and Right i.e. σ ∈ K1, iff for all t ∈ Wτ (X) we have Left(t) = Left(σ̂[t]) and Right(t) = Right(σ̂[t]). Then K1 is a submonoid of Hyp(τ). Let us consider the monoid Mhyp(τ,K1) of multi-hypersubstitutions, generated by K1. It is a submonoid of Mhyp(τ,Hyp(τ)). The variety RB of rectangular bands is K1-multi- solid. (ii) Let V str : Wτ (X) → X∗ be a mapping, which assigns to each term t the string of the variables in t. For instance, if t = f(x1, g(f(x1, x2), x3, x2), x4), then V str(t) = x1x1x2x3x2x4. This mapping is defined inductively as follows: if t = xj ∈ X, then V str(t) := xj ; and if t = f(t1, . . . , tn), then V str(t) := V str(t1)V str(t2) . . . V str(tn). Let K2 ⊂ Hyp(τ) be the set of all hypersubstitutions which preserve V str i.e. σ ∈ K2, if and only if for each t ∈ Wτ (X) it holds V str(t) = V str(σ̂[t]). Then K2 is a submonoid of Hyp(τ). Let us consider the monoid Mhyp(τ,K2) of multi-hypersubstitutions, generated by K2. It is a submonoid of Mhyp(τ,Hyp(τ)) and K2 ⊆ K1. It is not difficult to prove that the variety RB is K2-multi-solid. Finally, let us note that if Σ is the set of identities satisfied in RB, and if we add to K1 and K2 the hypersubstitution σ ∈ Hyp(τ) with σ(f) = f(x2, x1), then M1 := K1∪{σ} and M2 := K2∪{σ} are monoids, again such that χc M1 [Σ] = Id(τ), but χc M2 [Σ] 6= Id(τ). Jo u rn al A lg eb ra D is cr et e M at h .Sl. Shtrakov 129 3. Tree automata realization We consider an automata realization of the multi-hypersubstitutions. This concept will allow to use computer programmes in the case of fi- nite monoids of hypersubstitutions to obtain the images of terms under multi-hypersubstitutions. In Computer Science terms are used as data structures and they are called trees. The operation symbols are labels of the internal nodes of trees and variables are their leaves. The concept of tree automata was introduced in the 1960s in various papers such as [10]. Gécseg & Steinby’s book [6] is a good survey of the theory of tree automata and [3] is a development of this theory. Tree automata are classified as tree recognizers and tree transducers. Our aim is to define tree automata which interpret the application of multi- hypersubstitutions of the colored terms of a given type. Definition 9. A colored tree transducer of type τ is a tuple A = 〈X,F , P 〉 where as usual X is a set of variables, F is a set of operation symbols and P is a finite set of productions (rules of derivation) of the forms (i) x→ x, x ∈ X; (ii) 〈f, q〉(ξ1, · · · , ξn)→ 〈r, αr〉(ξ1, · · · , ξn), with 〈r, αr〉(ξ1, · · · , ξn) ∈W c τ (X ∪ χm), 〈f, q〉 ∈ Fc, ξ1, · · · , ξn ∈ χn, where χn = {ξ1, · · · , ξn} is an auxiliary alphabet. (All auxiliary variables ξj belong to a set χm = {ξ1, · · · , ξm} where m = maxar is the maximum of the arities of all operation symbols in F .) Definition 10. Let M ⊆ Hyp(τ) be a submonoid of Hyp(τ) and ρ ∈ Mhyp(τ,M) be a multi-hypersubstitution over M . A colored tree trans- ducer Aρ = 〈X,F , P 〉 is called Mh−transducer over M , if for the rules (ii) in P we have r = σ(q)(f) and αr(p) = q for all p ∈ PosF (r). The Mh−transducer Aρ runs over a colored term 〈t, αt〉 starting at the leaves of t and moves downwards, associating along the run a resulting colored term (image) with each subterm inductively: if t = x ∈ X then the Mh−transducer Aρ associates with t the term x ∈ W c τ (X), if x → x ∈ P ; if 〈t, αt〉 = 〈f, q〉(〈t1, αt1〉 . . . , 〈tn, αtn〉) then with 〈t, αt〉 the Mh−transducer Aρ associates the colored term 〈s, αs〉 = 〈u, αu〉(〈t1, αt1〉 . . . , 〈tn, αtn〉), if 〈f, q〉(ξ1, . . . , ξn)→ 〈u, αu〉(ξ1, · · · , ξn) ∈ P , where u = σ(q)(f) and αu(p) = q for all p ∈ PosF (u). For trees 〈t, αt〉, and 〈s, αs〉 we say 〈t, αt〉 directly derives 〈s, αs〉 by Aρ, if 〈s, αs〉 can be obtained from 〈t, αt〉 by replacing of an occurrence of a subtree 〈f, q〉(〈r1, αr1 〉, · · · , 〈rn, αrn〉), in 〈t, αt〉 by 〈u, αu〉(〈r1, αr1 〉, · · · , 〈rn, αrn〉) ∈W c τ (X ∪ χm). Jo u rn al A lg eb ra D is cr et e M at h .130 Multi-Solid Varieties and Mh-transducers If 〈t, αt〉 directly derives 〈s, αs〉 in Aρ, we write 〈t, αt〉 →Aρ 〈s, αs〉. Furthermore, we say 〈t, αt〉 derives 〈s, αs〉 in Aρ, if there is a sequence 〈t, αt〉 →Aρ 〈s1, αs1 〉 →Aρ 〈s2, αs2 〉 →Aρ · · · →Aρ 〈sn, αsn〉 = 〈s, αs〉 of direct derivations or if 〈t, αt〉 = 〈s, αs〉. In this case we write 〈t, αt〉 ⇒ ∗ Aρ 〈s, αs〉. Clearly, ⇒∗ Aρ is the reflexive and transitive closure of →Aρ . Let us denote by Thyp(τ,M) the set of all Mh−transducers of type τ over M. A term 〈t, αt〉 is translated to the term 〈s, αs〉 by the Mh−transducer Aρ if there exists a run of Aρ such that it associates with 〈t, αt〉 the colored term 〈s, αs〉. In this case we will write Aρ(〈t, αt〉) = 〈s, αs〉. Lemma 5. Aρ(〈t, αt〉) = 〈s, αs〉 ⇐⇒ ρ[〈t, αt〉] = 〈s, αs〉. Proof. For a variable-term x we have Aρ(x) = x = ρ[x]. Suppose that for i = 1, . . . , n we have Aρ(〈ti, αti〉) = ρ[〈ti, αti〉]. Then we obtain Aρ(〈f, q〉(〈t1, αt1〉, . . . , 〈tn, αtn〉)) = Aρ(〈f, q〉)(Aρ(〈t1, αt1〉), . . . , A ρ(〈tn, αtn〉)) = ρ[〈t, αt〉] = ρ[〈t, αt〉], where αt(ε) = q and αt[i] = αti for i = 1, . . . , n. The product (superposition) of two Mh−transducers Aρ1 and Aρ2 is defined by the following equation Aρ1 ◦Aρ2(〈t, αt〉) := Aρ1(Aρ2(〈t, αt〉)). Lemma 6. Let M ⊆ Hyp(τ) be a monoid of hypersubstitutions. Then the superposition of Mh−transducers of a given type is associative i.e. Aρ1 ◦ (Aρ2 ◦Aρ3)(〈t, αt〉) = (Aρ1 ◦Aρ2) ◦Aρ3(〈t, αt〉) for all ρ1, ρ2, ρ3 ∈MHyp(τ,M) and for all 〈t, αt〉 ∈W c τ (X). Theorem 6. Let M ⊆ Hyp(τ) be a monoid of hypersubstitutions. Then the set Thyp(τ,M) is a monoid which is isomorphic to the monoid of all multi-hypersubstitutions over M i.e. Thyp(τ,M) ∼= Mhyp(τ,M). Proof. We define a mapping ϕ : Mhyp(τ,M)→ Thyp(τ,M) by ϕ(ρ) := Aρ. To show that ϕ is a homomorphism we will prove that Aρ1 ◦ Aρ2 = Aρ1◦chρ2 , so that ϕ(ρ1) ◦ ϕ(ρ2) = ϕ(ρ1 ◦ch ρ2). We have Aρ1 ◦ Aρ2(〈t, αt〉) = Aρ1(Aρ2(〈t, αt〉)) = Aρ1(ρ2[〈t, αt〉]) = ρ1[ρ2[〈t, αt〉]] = ρ1 ◦ch ρ2[〈t, αt〉] = Aρ1◦chρ2(〈t, αt〉). Jo u rn al A lg eb ra D is cr et e M at h .Sl. Shtrakov 131 To see that ϕ is one-to-one, let Aρ1 = Aρ2 . Then from Lemma 5 for all 〈t, αt〉 ∈ W c τ (X) we have ρ1[〈t, αt〉] = ρ2[〈t, αt〉]. Hence for all f ∈ F and q ∈ IN we have ρ1[〈f, q〉] = ρ2[〈f, q〉] and therefore ρ1 = ρ2. References [1] G. Birkhoff, Lattice theory, (3rd ed.) Amer. Math. Soc., Providence, 1967 [2] S. Burris and H. Sankappanavar, A Course in Universal Algebra, The millennium edition, 2000 [3] H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, M. Tommasi,Tree Automata, Techniques and Applications, 1999, http://www.grappa.univ-lille3.fr/tata/ [4] K. Denecke, J. Koppitz and Sl. Shtrakov, Multi-Hypersubstitutions and Coloured Solid Varieties, J. Algebra and Computation, J. Algebra and Computation, Vol- ume 16, Number 4, August, 2006, pp.797-815. [5] K. Denecke, D. Lau, R. Pöschel and D. Schweigert, Hyperidentities, Hyperequa- tional Classes and Clone Congruences,General Algebra 7, Verlag Hölder-Pichler- Tempsky, Wien 1991, Verlag B.G. Teubner Stuttgart, pp.97-118 [6] F. Gécseg, M. Steinby, Tree Automata, Akadémiai Kiadó, Budapest 1984 [7] E. Graczýnska, On connection between identities and hyperidentities, Bull.Sect.Logic 17(1988),34-41. [8] G. Gratzer, Universal Algebra, D. van Nostrand Co., Princetown, 1968. [9] R. McKenzie, G. Mc Nulty and W. Taylor, Algebras, Lattices, Varieties, Vol. I, Belmont, California 1987. [10] J. W. Thatcher and J.B. Wright, Generalized finite automata, Notices Amer. Math. Soc., 12. (1965), abstract No. 65T-649,820. Contact information Sl. Shtrakov Dept. of Computer Sciences, South-West University, 2700 Blagoevgrad, Bulgaria E-Mail: shtrakov@aix.swu.bg URL: http://shtrakov.swu.bg Received by the editors: 03.04.2007 and in final form 25.01.2008.

Multi-solid varieties and Mh-transducers

Репозитарії

Схожі ресурси