Presentations and word problem for strong semilattices of semigroups

Let I be a semilattice, and Si (i ∈ I) be a family of disjoint semigroups. Then we prove that the strong semilattice S = S[I, Si , φj,i] of semigroups Si with homomorphisms φj,i : Sj → Si (j ≥ i) is finitely presented if and only if I is finite and each Si (i ∈ I) is finitely presented. Moreove...

Повний опис

Збережено в:
Бібліографічні деталі
Опубліковано в: :Algebra and Discrete Mathematics
Дата:2005
Автори: Ayık, G., Ayık, H., Unlu, Y.
Формат: Стаття
Мова:English
Опубліковано: Інститут прикладної математики і механіки НАН України 2005
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/157334
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Presentations and word problem for strong semilattices of semigroups / G. Ayık, H. Ayık, Y. Unlu // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 4. — С. 28–35. — Бібліогр.: 11 назв. — англ.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-157334
record_format dspace
spelling Ayık, G.
Ayık, H.
Unlu, Y.
2019-06-20T02:30:48Z
2019-06-20T02:30:48Z
2005
Presentations and word problem for strong semilattices of semigroups / G. Ayık, H. Ayık, Y. Unlu // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 4. — С. 28–35. — Бібліогр.: 11 назв. — англ.
1726-3255
2000 Mathematics Subject Classification: 20M05.
https://nasplib.isofts.kiev.ua/handle/123456789/157334
Let I be a semilattice, and Si (i ∈ I) be a family of disjoint semigroups. Then we prove that the strong semilattice S = S[I, Si , φj,i] of semigroups Si with homomorphisms φj,i : Sj → Si (j ≥ i) is finitely presented if and only if I is finite and each Si (i ∈ I) is finitely presented. Moreover, for a finite semilattice I, S has a soluble word problem if and only if each Si (i ∈ I) has a soluble word problem. Finally, we give an example of nonautomatic semigroup which has a soluble word problem.
en
Інститут прикладної математики і механіки НАН України
Algebra and Discrete Mathematics
Presentations and word problem for strong semilattices of semigroups
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Presentations and word problem for strong semilattices of semigroups
spellingShingle Presentations and word problem for strong semilattices of semigroups
Ayık, G.
Ayık, H.
Unlu, Y.
title_short Presentations and word problem for strong semilattices of semigroups
title_full Presentations and word problem for strong semilattices of semigroups
title_fullStr Presentations and word problem for strong semilattices of semigroups
title_full_unstemmed Presentations and word problem for strong semilattices of semigroups
title_sort presentations and word problem for strong semilattices of semigroups
author Ayık, G.
Ayık, H.
Unlu, Y.
author_facet Ayık, G.
Ayık, H.
Unlu, Y.
publishDate 2005
language English
container_title Algebra and Discrete Mathematics
publisher Інститут прикладної математики і механіки НАН України
format Article
description Let I be a semilattice, and Si (i ∈ I) be a family of disjoint semigroups. Then we prove that the strong semilattice S = S[I, Si , φj,i] of semigroups Si with homomorphisms φj,i : Sj → Si (j ≥ i) is finitely presented if and only if I is finite and each Si (i ∈ I) is finitely presented. Moreover, for a finite semilattice I, S has a soluble word problem if and only if each Si (i ∈ I) has a soluble word problem. Finally, we give an example of nonautomatic semigroup which has a soluble word problem.
issn 1726-3255
url https://nasplib.isofts.kiev.ua/handle/123456789/157334
citation_txt Presentations and word problem for strong semilattices of semigroups / G. Ayık, H. Ayık, Y. Unlu // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 4. — С. 28–35. — Бібліогр.: 11 назв. — англ.
work_keys_str_mv AT ayıkg presentationsandwordproblemforstrongsemilatticesofsemigroups
AT ayıkh presentationsandwordproblemforstrongsemilatticesofsemigroups
AT unluy presentationsandwordproblemforstrongsemilatticesofsemigroups
first_indexed 2025-11-25T22:33:41Z
last_indexed 2025-11-25T22:33:41Z
_version_ 1850567661683998720
fulltext Jo u rn al A lg eb ra D is cr et e M at h . Algebra and Discrete Mathematics RESEARCH ARTICLE Number 4. (2005). pp. 28 – 35 c© Journal “Algebra and Discrete Mathematics” Presentations and word problem for strong semilattices of semigroups Gonca Ayık, Hayrullah Ayık and Yusuf Ünlü Communicated by V. I. Sushchansky Abstract. Let I be a semilattice, and Si (i ∈ I) be a family of disjoint semigroups. Then we prove that the strong semilattice S = S[I, Si, φj,i] of semigroups Si with homomorphisms φj,i : Sj → Si (j ≥ i) is finitely presented if and only if I is finite and each Si (i ∈ I) is finitely presented. Moreover, for a finite semilattice I, S has a soluble word problem if and only if each Si (i ∈ I) has a soluble word problem. Finally, we give an example of non- automatic semigroup which has a soluble word problem. Introduction Finite presentability of semigroup constructions has been widely studied in recent years (see, for example, [1, 2, 8, 9, 10]). One of semigroup structures is a strong semilattice of semigroups which is an important structure for completely regular semigroups (see [7]). Let I be a semilattice, and let Si (i ∈ I) be a family of disjoint semigroups. Suppose that, for any two elements i, j ∈ I, with i ≤ j (i ≤ j if and only if ij = i), there is a homomorphism φj,i : Sj −→ Si, and that these homomorphisms satisfy the following conditions: 1. for each i ∈ I, φi,i is the identity map 1Si ; 2. for all i, j, k ∈ I, such that i ≤ j ≤ k, φk,jφj,i = φk,i. 2000 Mathematics Subject Classification: 20M05. Key words and phrases: Semigroup presentations, strong semilattices of semi- groups, word problems.. Jo u rn al A lg eb ra D is cr et e M at h .G. Ayık, H. Ayık, Y. Ünlü 29 Define a multiplication on S = ∪i∈ISi in terms of the multiplications in the components Si and the homomorphisms φj,i, by the rule that, for each x ∈ Si and y ∈ Sj , xy = (xφi,ij)(yφj,ij). Respect to this multiplication, S is a semigroup, called a strong semi- lattice of semigroups, and denoted by S[I; Si, φj,i]. Finite presentability of strong semilattice of semigroups was investigated in [1]. The authors of [1] first proved that a band of semigroups Si (i ∈ I) is finitely pre- sented if I is finite and each Si is finitely presented (see [1, Corollary 4.5]). Moreover, they proved that a band of monoids Si (i ∈ I) is fi- nitely presented if and only if I is finite and each Si is finitely presented (see [1, Corollary 5.6]). Then, from Theorem 1.3 in [11] they concluded that a strong semilattice of semigroups S[I; Si, φj,i] is finitely presented if each Si (i ∈ I) is finitely presented and if I is finite. In this paper we construct more specific presentations for strong semilattice of semigroups from given presentations for Si (i ∈ I) and a presentation for each Si from a given presentation for S[I; Si, φj,i]. Moreover, if S[I; Si, φj,i] is finitely generated then we prove that S[I; Si, φj,i] has a soluble word problem if and only if each Si has a soluble word problem. 1. The presentations For a given alphabet A, let A+ be the free semigroup on A (i.e. the set of all non-empty words over A) and let A∗ be the free monoid on A (i.e. A+ together with the empty word, denoted by ε). A semigroup presentation is a pair 〈A | R〉, with R ⊆ A+ × A+. A semigroup S is defined by the presentation 〈A | R〉 if S is isomorphic to the semigroup A+/ρ, where ρ is the congruence on A+ generated by R. For any two words w1, w2 ∈ A+ we write w1 ≡ w2 if they are identical words and write w1 = w2 if w1ρ = w2ρ (i.e. if they represent the same element in S). It is well known that w1 = w2 if and only if this relation is a consequence of R, that is there is a finite sequence w1 ≡ η1, η2, ..., ηk ≡ w2 of words from A+, in which every term ηi (1 < i ≤ k) is obtained from the previous one by applying one relation from R. Let P = 〈A | R〉 be a presentation for S and let W ⊆ A+. If W contains exactly one element representing each element of S then W is called a canonical form for S respect to P. The semigroup S is finitely presented if S has a presentation 〈A | R〉 such that both A and R are finite. A (finite) monoid presentation is defined similarly with respect to the free monoid A∗. Notice that a monoid M is finitely presented as a monoid if and only if it is finitely presented as Jo u rn al A lg eb ra D is cr et e M at h .30 Presentations and word problem for strong ... a semigroup. Furthermore, if 〈A | R〉 is a semigroup presentation for a monoid M then 〈A | R, w = 1〉 is a monoid presentation for M, where w ∈ A+ is a word representing the identity of M . Now we construct a presentation for S = S[I; Si, φj,i] from given presentations 〈Ai | Ri〉 for Si (i ∈ I). Since S is a disjoint union of semigroups Si (i ∈ I), it is clear that A = ∪i∈IAi generates S. For simplicity of notation we assume that Ai ⊆ Si. Consider the following presentation P = 〈A | R, aiaj = (aiφi,ij)(ajφj,ij) (ai ∈ Ai, aj ∈ Aj)〉 where A = ∪i∈IAi and R = ∪i∈IRi. Proposition 1. With above notation if a ∈ Ai and u ∈ A+ j with i 6= j, then there exists v ∈ A+ ij such that the relation ua = v is a consequence of the relations aja = (ajφj,ij)(aφi,ij) (a ∈ Ai, aj ∈ Aj). Proof. We use induction on the length of u. If | u |= 1 then take v ≡ (uφj,ij)(aφi,ij). Next we suppose that u ≡ a1 · · · an (a1, . . . , an ∈ Aj) with n ≥ 2 and that the result is true for any word of length n − 1. By the inductive hypothesis, there exists bv1 with b ∈ Aij and v1 ∈ A∗ ij such that the relation (a2 · · · an)a = bv1 is a consequences of the relations aja = (ajφj,ij)(aφi,ij) (a ∈ Ai, aj ∈ Aj). Since jij = ij in I and φij,ij is the identity map on Sij , it follows that ua ≡ a1((a2 · · · an)a) = (a1b)v1 = ((a1φj,jij)(bφij,jij)v1 ≡ ((a1φj,ij)b)v1. Since (a1φj,ij) ∈ A+ ij , taking v ≡ (a1φj,ij)bv1 completes the proof. Proposition 2. If u ≡ ai1 · · · aim (ai1, . . . , aim ∈ A ) and k = i1 · · · im, then there exists u ∈ A+ k such that the relation u = u is a consequence of the relations aiaj = (aiφi,ij)(ajφj,ij) (ai ∈ Ai, aj ∈ Aj). Proof. We use induction on m. If m = 1 then we take u ≡ u ≡ ai1 . Now we suppose that m ≥ 2 and that the result is true for m − 1. Let k1 = i1 · · · im−1. By inductive hypothesis there exists u1 ∈ A+ k1 such that the relation u1 ≡ ai1 · · · aim−1 = u1 is a consequence of the relations aiaj = (aiφi,ij)(ajφj,ij) (ai ∈ Ai, aj ∈ Aj). By the previous proposition there exists u ∈ A+ k1im such that u1aim = u. Since k1im = k, for u ∈ A+ k we have u ≡ (ai1 · · · aim−1 )aim = u1aim = u, as required. Theorem 1. Let S[I; Si, φj,i] be a strong semilattice of semigroups and let Pi = 〈 Ai | Ri 〉, with Ai ∩Aj = ∅ for i 6= j, be a semigroup presentation for Si (i ∈ I). If we take A = ∪i∈IAi and R = ∪i∈IRi then P = 〈A | R, aiaj = (aiφi,ij)(ajφj,ij) (ai ∈ Ai, aj ∈ Aj with i 6= j)〉 is a presentation for S[I; Si, φj,i]. Jo u rn al A lg eb ra D is cr et e M at h .G. Ayık, H. Ayık, Y. Ünlü 31 Proof. It is clear that A generates S[I; Si, φj,i] and that all the relations in P hold in S[I; Si, φj,i]. Notice that since φi,i is the identity map on Si and i2 = i (i ∈ I), we can consider P as 〈A | R, aiaj = (aiφi,ij)(ajφj,ij) (ai ∈ Ai, aj ∈ Aj)〉 (i.e. without conditions i 6= j). Let u and v be any two words in A+ such that u = v holds in S[I; Si, φj,i], that is they represent the same element of S[I; Si, φj,i]. By Proposition 2, there exist k, l ∈ I, u ∈ A+ k and v ∈ A+ l such that u = u and v = v are consequences of the relations (aiφi,ij)(ajφj,ij) (ai ∈ Ai, aj ∈ Aj). Since the relation u = v holds in both Sk and Sl, we have k = l and u = v as a consequence of Rk. Therefore u = v is a consequence of relations in P, as required. Notice that if Wi ⊆ A+ i (i ∈ I) is a set of canonical forms for Si (i ∈ I) with respect to 〈 Ai | Ri 〉, then W = ∪i∈IWi is a set of canonical forms for S = S[I; Si, φj,i] with respect to P. Now we find a presentation for each Si (i ∈ I) from a presentation for S = S[I; Si, φj,i]. Proposition 3. Let A be a generating set for S = S[I; Si, φj,i] and Bj = {a ∈ A | a ∈ Sj} (j ∈ I). Then, for each i ∈ I, Ai = ⋃ j≥i {aj,i ∈ Si | aj ∈ Bj and ajφj,i = aj,i} generates Si. Proof. Since Ai ⊂ Si, it is enough to show that Si ⊆ 〈Ai〉. For s ∈ Si, there exist ai(1), . . . , ai(m) ∈ A such that s = ai(1) · · · ai(m). By the multiplication defined on S, we must have i(1), . . . , i(m) ≥ i and there exists at least one k ∈ {1, . . . , m} such that i(k) = i, and so s = ai(1) · · · ai(m) = (ai(1)φi(1),i) · · · (ai(m)φi(m),i) ≡ ai(1),i · · · ai(m),i ∈ 〈Ai〉, as required. Notice that aiφi,i = ai,i ≡ ai. Moreover, for aj , a ′ j ∈ Bj , aj 6= a′j it is possible to obtain ajφj,i = a′jφj,i. For every aj,i ∈ Ai, we fix aj ∈ Bj such that ajφj,i = aj,i and denote this fixed aj by aj,i. Let 〈A | R〉 be a finite presentation for S = S[I; Si, φj,i]. Next we construct a presentation for Si (i ∈ I) in terms of Ai. Let Φi be the unique homomorphism from ( ⋃ j≥i Bj )+ to A+ i such that, for each a ∈ Bj , j ≥ i, aΦi = aφj,i, and let Wi = ( ⋃ j≥i Bj )∗ Bi ( ⋃ j≥i Bj )∗ . Notice that, for w ∈ A+, w represent an element of Si if and only if w ∈ Wi. Jo u rn al A lg eb ra D is cr et e M at h .32 Presentations and word problem for strong ... Theorem 2. Let Q = 〈A | R〉 be a presentation for S = S[I; Si, φj,i]. With above notation, Qi = 〈Ai | {(rΦi, sΦi) | (r, s) ∈ R ∩ (   ⋃ j≥i Bj   ∗ ×   ⋃ j≥i Bj   ∗ )}〉 is a presentation for Si (i ∈ I). Proof. By Proposition 3, Ai is a generating set for Si. Let Ri = {(rΦi, sΦi) | (r, s) ∈ R ∩ (   ⋃ j≥i Bj   ∗ ×   ⋃ j≥i Bj   ∗ )}. It is clear that all the relation in Ri hold in Si. For u ≡ aj(1),i · · · aj(m),i and v ≡ aλ(1),i · · · aλ(n),i where aj(1),i, . . . , aj(m),i, aλ(1),i, . . . , aλ(n),i ∈ Ai, let the relation u = v holds in Si. To complete the proof we have to show that u = v is a consequence of Ri. Let u,v ∈ A+ denote the words A+ obtained from u and v by replacing aj,i by aj,i, respectively. It is clear that the relation u = v holds in S, and so there is a finite sequence u ≡ α1, α2, ..., αm ≡ v of words from A+, in which every term αk+1 (1 ≤ k < m) is obtained from αk by applying one relation from R. If αk ≡ βkrkγk and αk+1 ≡ βkskγk where βk, γk ∈ A∗ and (rk, sk) ∈ R (or equivalently (sk, rk) ∈ R) then βk, γk, rk and sk must be in ( ⋃ j≥i Bj )∗ . Thus αkΦi ≡ (βkΦi)(rkΦi)(γkΦi) and αk+1Φi ≡ (βkΦi)(skΦi)(γkΦi) where βkΦi, γkΦi ∈ A∗ i and (rkΦi, skΦi) ∈ Ri (or equivalently (skΦi, rkΦi) ∈ Ri), and so we have a finite sequence u ≡ α1Φi, α2Φi, ..., αmΦi ≡ v of words from A+ i . Hence u = v is a consequence of Ri, as required. With above notation notice that if Wi = ( ⋃ j≥i Bj )∗ Bi ( ⋃ j≥i Bj )∗ then, for w ∈ A+, w represent an element of Si if and only if w ∈ Wi. Since there exist finitely many Bi, there exist finitely many Wi so that I is finite and every Qi (i ∈ I) in Theorem 2 is a finite presentation whenever Q is a finite presentation. Moreover, the presentation P in Theorem 1 is finite if I is finite and every Pi is finite. Therefore, we have the following corollary. Corollary 1. The strong semilattice S[I; Si, φj,i] of disjoint semigroups Si (i ∈ I) is finitely presented if and only if I is finite and every Si is finitely presented. Jo u rn al A lg eb ra D is cr et e M at h .G. Ayık, H. Ayık, Y. Ünlü 33 2. Word Problem A finitely generated semigroup S is said to have a soluble word problem with respect to a finite generating set A if there exists an algorithm which, for any two words u, v ∈ A+, decides whether or not the relation u = v holds in S (in finite steps). It is easy to see that the solubility of the word problem does not depend on the choice of the finite generating set for a finitely generated semigroup ([11]). Theorem 3. Let I be a finite semilattice, and let Si (i ∈ I) be a fam- ily of disjoint finitely generated semigroups. The strong semilattice S = S[I; Si, φj,i] has a soluble word problem if and only if, for each i ∈ I, Si has a soluble word problem. Proof. (⇒) Suppose that S = S[I; Si, φj,i] has a soluble word problem. Let Ai be a finite generating set for Si. We know that A = ⋃ i∈I Ai is a finite generating set for S. Then S has a soluble word problem with respect to generating set A. Since, for each i ∈ I, if u, v ∈ A+ i , then u, v ∈ A+ and there exists an algorithm which decides whether or not u = v holds in S and so in Si. Thus Si has a soluble word problem. (⇐) Suppose that, for each i ∈ I, Si has a soluble word problem and Bi is a finite generating set for Si. Let Ai = ⋃ j≥i Bjφj,i for each i ∈ I. It is clear that, for each i ∈ I, Ai is a finite generating set for Si, and moreover, Si has a soluble word problem with respect to the generating set Ai. Then we show that S = S[I; Si, φj,i] has a soluble word problem with respect to the generating set A = ⋃ i∈I Ai. Let u, v ∈ A+ be any two words. Then we have u ≡ ai(1) · · · ai(m) and v ≡ aj(1) · · · aj(n) where ai(k) ∈ Ai(k) and aj(l) ∈ Aj(l) (1 ≤ k ≤ m, 1 ≤ l ≤ n). Take i = i(1) · · · i(n) and j = j(1) · · · j(n). Since u represents an element of Si and v represents an element of Sj , if i 6= j, then by the mul- tiplication defined on S, u = v does not hold in S. Now suppose that i = j and take u ≡ (ai(1)φi(1),i) · · · (ai(m)φi(m),i) ∈ A+ i and v ≡ (aj(1)φj(1),j) · · · (aj(m)φj(m),j) ∈ A+ i . Since u = u and v = v holds in S, u = v holds in S if and only if u = v holds in Si. Since, for each i ∈ I, Si has a soluble word problem with respect to Ai, there exists an algorithm which decides whether u = v holds in Si in finite steps. Therefore S has a soluble word problem. Automatic semigroups were first introduced in [5] and they have been widely studied for semigroup structures, such as direct product of semi- groups, Rees matrix semigroups, etc. (see [4, 6]). It is shown that if a semigroup S is automatic then S has a soluble word problem (see [5, Jo u rn al A lg eb ra D is cr et e M at h .34 Presentations and word problem for strong ... Corollary 3.7]). In general the converse of Corollary 3.7 in [5] is not true. For this, consider the free group G1 = 〈a, b | 〉 of rank two and the free product G2 = 〈c, d | c2 = 1 d2 = 1〉 of two cyclic groups of order two. It is a well-known fact that free groups of finite rank, and finite groups has soluble word problem. In addition, the free product of two groups which have soluble word problems has also soluble word problem. Therefore, G1 and G2 have soluble word problems. Moreover the groups G1 and G2 are automatic (see [3]). Let φ1,2 : G1 → G2 be the homomorphism defined by aφ1,2 = c and bφ1,2 = d, φ1,1 be the identity map of G1, φ2,2 be the identity map of G2. Then consider the strong semilattice G = S[I; Gi, φj,i] of the groups G1 and G2 where I = {1, 2} is the semilattice with the multiplication i ·j = max{i, j}. It follows from Theorem 3 that the strong semilattice G of the groups G1 and G2 has a soluble word problem however it is shown that G is not automatic (see [6]). References [1] I.M. Araujo, M.J.J. Branco, V.H. Fernandes, G.M.S. Gomes, N. Ruskuc, On Generators and Relations of Unions of Semigroups, Semigroup Forum, 63, 2001, pp. 49-62. [2] H. Ayık, N. Ruskuc, Generators and Relations of Rees Matrix Semigroups, Proc. Edinburgh Math. Soc., 42, 1999, pp. 482-495. [3] G. Baumslag, S.M. Gersten, M. Shapiro, H. Short, Automatic Groups and Amal- gams, J. Pure Appl. Algebra 76, 1991, pp. 229-316. [4] C.M. Campbell, E.F. Robertson, N. Ruskuc, R.M. Thomas, Direct Products of Automatic Semigroups, J. Austral. Math. Soc., 69, 2000, pp. 19-24. [5] C.M. Campbell, E.F. Robertson, N. Ruskuc, R.M. Thomas, Automatic Semi- groups, Theoret. Comput. Sci., 250, 2001, pp. 365-391. [6] C.M. Campbell, E.F. Robertson, N. Ruskuc, R.M. Thomas, Automatic Com- pletely Simple Semigroups, Acta Math. Hungar., 95, 2002, pp. 201-215. [7] J.M. Howie, Fundamentals of Semigroup Theory, Clarendon Press, 1995. [8] J.M. Howie, N. Ruskuc, Constructions and Presentations for Monoids, Comm. Algebra, 22, 1994, pp. 6209-6224. [9] T.G. Lavers, Presentations of General Products of Monoids, J. Algebra, 204, 1998, pp. 733-741. [10] E.F. Robertson, N. Ruskuc, J. Wiegold, Generators and Relations of Direct Prod- uct of Semigroups, Trans. Amer. Math. Soc., 350, 1998, pp. 2665–2685. [11] N. Ruskuc, On Large Subsemigroups and Finiteness Conditions of Semigroups, Proc. London Math. Soc., 76, 1998, pp. 383–405. Jo u rn al A lg eb ra D is cr et e M at h .G. Ayık, H. Ayık, Y. Ünlü 35 Contact information G. Ayık Çukurova University, Department of Math- ematics, 01330-Adana, Turkey E-Mail: agonca@cu.edu.tr H. Ayık Çukurova University, Department of Math- ematics, 01330-Adana, Turkey E-Mail: hayik@cu.edu.tr Y. Ünlü Çukurova University, Department of Math- ematics, 01330-Adana, Turkey E-Mail: yusuf@cu.edu.tr Received by the editors: 12.09.2005 and final form in 15.12.2005.