A necessary condition to test the minimality of generalized linear sequential machines using the theory of near-semirings

In this work first we study the properties of nearsemirings to introduce an α-radical. Then we observe the role of near-semirings in generalized linear sequential machines, and we test the minimality through the radical.

Збережено в:

Бібліографічні деталі
Дата:	2005
Автори:	Krishna, K.V., Chatterjee, N.
Формат:	Стаття
Мова:	English
Опубліковано:	Інститут прикладної математики і механіки НАН України 2005
Назва видання:	Algebra and Discrete Mathematics
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/157196
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	A necessary condition to test the minimality of generalized linear sequential machines using the theory of near-semirings / K.V. Krishna, N. Chatterjee // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 3. — С. 30–45. — Бібліогр.: 7 назв. — англ.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-157196
record_format	dspace
spelling	irk-123456789-1571962019-06-20T01:28:34Z A necessary condition to test the minimality of generalized linear sequential machines using the theory of near-semirings Krishna, K.V. Chatterjee, N. In this work first we study the properties of nearsemirings to introduce an α-radical. Then we observe the role of near-semirings in generalized linear sequential machines, and we test the minimality through the radical. 2005 Article A necessary condition to test the minimality of generalized linear sequential machines using the theory of near-semirings / K.V. Krishna, N. Chatterjee // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 3. — С. 30–45. — Бібліогр.: 7 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 16Y99, 68Q70, 20M11, 20M35. http://dspace.nbuv.gov.ua/handle/123456789/157196 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
description	In this work first we study the properties of nearsemirings to introduce an α-radical. Then we observe the role of near-semirings in generalized linear sequential machines, and we test the minimality through the radical.
format	Article
author	Krishna, K.V. Chatterjee, N.
spellingShingle	Krishna, K.V. Chatterjee, N. A necessary condition to test the minimality of generalized linear sequential machines using the theory of near-semirings Algebra and Discrete Mathematics
author_facet	Krishna, K.V. Chatterjee, N.
author_sort	Krishna, K.V.
title	A necessary condition to test the minimality of generalized linear sequential machines using the theory of near-semirings
title_short	A necessary condition to test the minimality of generalized linear sequential machines using the theory of near-semirings
title_full	A necessary condition to test the minimality of generalized linear sequential machines using the theory of near-semirings
title_fullStr	A necessary condition to test the minimality of generalized linear sequential machines using the theory of near-semirings
title_full_unstemmed	A necessary condition to test the minimality of generalized linear sequential machines using the theory of near-semirings
title_sort	necessary condition to test the minimality of generalized linear sequential machines using the theory of near-semirings
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2005
url	http://dspace.nbuv.gov.ua/handle/123456789/157196
citation_txt	A necessary condition to test the minimality of generalized linear sequential machines using the theory of near-semirings / K.V. Krishna, N. Chatterjee // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 3. — С. 30–45. — Бібліогр.: 7 назв. — англ.
series	Algebra and Discrete Mathematics
work_keys_str_mv	AT krishnakv anecessaryconditiontotesttheminimalityofgeneralizedlinearsequentialmachinesusingthetheoryofnearsemirings AT chatterjeen anecessaryconditiontotesttheminimalityofgeneralizedlinearsequentialmachinesusingthetheoryofnearsemirings AT krishnakv necessaryconditiontotesttheminimalityofgeneralizedlinearsequentialmachinesusingthetheoryofnearsemirings AT chatterjeen necessaryconditiontotesttheminimalityofgeneralizedlinearsequentialmachinesusingthetheoryofnearsemirings
first_indexed	2025-07-14T09:35:11Z
last_indexed	2025-07-14T09:35:11Z
_version_	1837614457289703424
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. (2005). pp. 30 – 45 c© Journal “Algebra and Discrete Mathematics” A necessary condition to test the minimality of generalized linear sequential machines using the theory of near-semirings Kanduru Venkata Krishna and Niladri Chatterjee Communicated by V. A. Artamonov Abstract. In this work first we study the properties of near- semirings to introduce an α-radical. Then we observe the role of near-semirings in generalized linear sequential machines, and we test the minimality through the radical. Introduction Holcombe used the theory of near-rings to study linear sequential ma- chines of Eilenberg [1, 4]. Though the picture of near-rings in linear sequential machines is a natural extension of the syntactic semigroups, the decomposition of linear sequential machines, which is different from the one given by Eilenberg, enabled Holcombe to study these machines thoroughly using near-rings [4]. Holcombe established several properties of machines using near-rings. Indeed, he has introduced an α-radical of affine near-rings which plays an important role to test the minimal- ity of linear sequential machines [5]. The construction of the radical is motivated by Theorem 4.6 of [4], which can be read as: Let M = (Q,A,B, F,G) be a linear sequential machine. If M is min- imal then there is no proper nonzero N -submodule K of Q such that This work has been presented in the “69th Workshop on General Algebra", and “20th Conference for Young Algebraists" in Potsdam, March 18-20, 2005 with the title Near-Semirings in Generalized Linear Sequential Machines 2000 Mathematics Subject Classification: 16Y99, 68Q70, 20M11, 20M35. Key words and phrases: near-semiring, radical, linear sequential machine. Jo u rn al A lg eb ra D is cr et e M at h .K. V. Krishna, N. Chatterjee 31 G0(K) = {0}, where N is the syntactic near-ring of M and G0(q) = G(q, 0) ∀q ∈ Q. However, with the hypothesis of the above result, one can observe that there is no proper nonzero N -submodule of Q (cf. Theorem 4). This observation enables us to obtain an improvement in the α-radical. Indeed we are able to introduce an improved α-radical for near-semirings in a more general setup to study linear sequential machines. In order to extend the work for near-semirings, we formulated generalized linear sequential machines by replacing modules with semimodules in linear sequential machines. Even in this generalization, without losing much information, we could get all the results that have been obtained by Holcombe for linear sequential machines. Moreover, the radical obtained is much simpler. This paper is organized in four sections. In Section 1, we introduce fundamental notions in the theory of near-semirings, and prepare the background to study sequential machines. The tools and techniques of universal algebra [3] have been used to extend the notions of near- rings. Following van Hoorn, we have extended some of the notions of ideals for near-semirings, which have been defined for zero-symmetric near-semirings [6]. Section 2 is dedicated to introduce and study the properties of α-radicals of near-semirings. In Section 3, we generalize the notion of linear sequential machines and study the role of near-semirings via Holcombe’s decomposition of sequential machines, through minimiza- tion. Finally, in Section 4 we state how the α-radical provides a necessary condition to test the minimality of generalized linear sequential machines. 1. Near-semirings An algebraic structure (S,+, ·) is said to be a near-semiring if 1. (S,+) is a semigroup with identity 0, 2. (S, ·) is a semigroup, 3. (x+ y)z = xz + yz ∀x, y, z ∈ S, and 4. 0s = 0 ∀s ∈ S. Let (Γ,+) be an additive semigroup with zero. The set of all functions f : Γ −→ Γ, denoted by M(Γ), is a near-semiring with respect to point wise addition and composition of mappings. A near-semiring is a semiring if + is commutative, z(x+ y) = zx+ zy ∀x, y, z ∈ S, and s0 = 0 ∀s ∈ S [2]. Jo u rn al A lg eb ra D is cr et e M at h .32 Near-semirings in linear sequential machines In what follows S always denotes a near-semiring and Γ denotes an additive semigroup with zero. The notions of homomorphism and subnear-semiring can be defined in the usual way, respectively, as a mapping that preserves both the operations along with zero, and a subset with zero which is closed with respect to both the operations. The set of all constant mappings on Γ and the set of all mappings on Γ which fixes zero have importance in this work. In fact, they are subnear- semirings of M(Γ). Let us define these substructures in an arbitrary near-semiring S as follows. Define Sc = {s ∈ S \| s0 = s} and S0 = {s ∈ S \| s0 = 0}. Note that Sc and S0 are subnear-semiring of S. Moreover, ScS = Sc = SSc. In a near- semiring S, Sc and S0 are said to be constant and zero-symmetric parts respectively. A near-semiring S is said to be a constant near-semiring (zero-symmetric near-semiring) if S = Sc (S = S0). Remark 1. Sc = {s ∈ S \| st = s, ∀t ∈ S}. Define Sd = {x ∈ S \| x(y + z) = xy + xz ∀y, z ∈ S}. Note that Sd is a semigroup with respect to multiplication and 0 ∈ Sd. A subnear- semiring of S is said to be distributively generated if it is generated by a subsemigroup of Sd. Also, observe that Sd + Sc is a semigroup with respect to multiplication and 0 ∈ Sd + Sc. Remark 2. If + is commutative in (S,+, ·) then Sd is closed with respect to + and hence Sd is a subnear-semiring of S which is distributive. Also, in this case Sd + Sc is a subnear-semiring of S. Proposition 1. Suppose T = Td + Tc is a subsemigroup of Sd + Sc such that dt ∈ T for all d ∈ Td and t ∈ T , where Td ⊆ Sd and Tc ⊆ Sc. If 0 ∈ T then the subnear-semiring of S generated by T , 〈T 〉 = { n∑ i=1 ti \| ti ∈ T, n ≥ 1}. Proof. Since 〈T 〉 is contained in any subnear-semiring of S that contains T , and is closed with respect to addition, it is enough to observe that 〈T 〉 is closed with respect to multiplication. For di, d ′ j ∈ Td; ci, c ′ j ∈ Tc with Jo u rn al A lg eb ra D is cr et e M at h .K. V. Krishna, N. Chatterjee 33 1 ≤ i ≤ n, 1 ≤ j ≤ m, consider ( n∑ i=1 (di + ci) )  m∑ j=1 (d′j + c′j)   = n∑ i=1  di m∑ j=1 (d′j + c′j) + ci   = n∑ i=1   m−1∑ j=1 (di(d ′ j + c′j)) + di(d ′ m + c′m) + ci   = n∑ i=1   m−1∑ j=1 (di(d ′ j + c′j)) + (di + ci)(d ′ m + c′m)   Since T is a subsemigroup and TdT ⊆ T , for each 1 ≤ i ≤ n, 1 ≤ j ≤ m − 1; (di + ci)(d ′ m + c′m) and di(d ′ j + c′j) are in T . Thus the above expression is a finite sum of elements of T , so that 〈T 〉 is closed with respect to multiplication. Hence the result. Corollary 1. The subnear-semiring of S generated by Sd + Sc, 〈Sd + Sc〉 = { n∑ i=1 si \| si ∈ Sd + Sc, n ≥ 1}. Let us denote the set of endomorphisms of Γ by EndΓ. It is clear that EndΓ is a semigroup. Note that each element of EndΓ is a distributive element of M(Γ). Moreover, EndΓ = M(Γ)d. Indeed, if f ∈ M(Γ) is distributive then for γ1, γ2 ∈ Γ, f(γ1 + γ2) = f(γ̂1(γ) + γ̂2(γ)) = f(γ̂1 + γ̂2)(γ) = (fγ̂1 + fγ̂2)(γ) = f(γ1) + f(γ2), where γ̂1, γ̂2 are constant maps on Γ which take the values γ1, γ2 respec- tively and γ ∈ Γ is arbitrary. Let ConΓ be the set of all constant functions of M(Γ). ConΓ is a subnear-semiring of M(Γ) and M(Γ)ConΓ = ConΓ = ConΓM(Γ). Furthermore, ConΓ = M(Γ)c (cf. Remark 1). An element of M(Γ) is said to be an affine mapping if it is a sum of an endomorphism and a constant map on Γ. The set of affine mappings on Jo u rn al A lg eb ra D is cr et e M at h .34 Near-semirings in linear sequential machines Γ, denoted by Maff(Γ), i.e. Maff(Γ) = EndΓ + ConΓ, is a subsemigroup of M(Γ). The near-semiring generated by the semigroup EndΓ + ConΓ, denoted by EC(Γ), is defined as the affinely generated near-semiring. It is clear from the Corollary 1 that a typical element of EC(Γ) is of the form n∑ i=1 (ei + ci) for ei ∈ EndΓ, ci ∈ ConΓ. Remark 3. If (Γ,+) is commutative, then the set of affine mappings on Γ, Maff(Γ), is subnear-semiring of M(Γ). That is Maff(Γ) = EC(Γ). In this case we call Maff(Γ) as affine near-semiring. In general, a near-semiring S is said to be affine near-semiring if there exist a semiring E ⊆ S, and a constant near-semiring C ⊆ S such that S = E + C. A semigroup (Γ,+) is said to be an S-semigroup if there exists a composition (x, γ) 7→ xγ of S × Γ −→ Γ such that for all x, y ∈ S, γ ∈ Γ, 1. (x+ y)γ = xγ + yγ, 2. (xy)γ = x(yγ), and 3. 0γ = 0Γ, where 0Γ is the zero of Γ. It is clear that Γ is an S-semigroup with S = M(Γ). The semigroup (S,+) of a near-semiring (S,+, ·) is an S-semigroup. We denote this S-semigroup by S+. A subsemigroup ∆ of an S-semigroup Γ is such that S∆ ⊆ ∆ then we say it is an S-subsemigroup of Γ. An S-morphism of an S-semigroup Γ is a semigroup morphism ϕ of Γ into an S-semigroup Γ′ such that ϕ(xγ) = xϕ(γ) for all γ ∈ Γ and x ∈ S. Note that ϕ(0Γ) = 0Γ′ . Indeed, ϕ(0Γ) = ϕ(00Γ) = 0ϕ(0Γ) = 0Γ′ . Following van Hoorn, we extend some of the notions of ideals, which are appropriate in this context, from zero-symmetric near-semirings to near-semirings. For details on ideals of zero-symmetric near-semiring one may refer [6]. An ideal of a near-semiring is defined as the kernel of a near-semiring homomorphism. The kernel of an S-morphism is called as S-kernel of Γ. The S-kernels of the S-semigroup S+ are called left ideals of S. A right invariant left ideal of S is called as a weak ideal of S. Note that every ideal of S is a weak ideal. Jo u rn al A lg eb ra D is cr et e M at h .K. V. Krishna, N. Chatterjee 35 Theorem 1. The annihilator A(∆) of a non-void subset ∆ of an S- semigroup Γ is a left ideal of S+. Proof. Since A(∆) = ⋂ {A(δ) \| δ ∈ ∆}, it is enough to show that, for δ ∈ ∆, A(δ) is an S-kernel of S+. Observe that the mapping x 7→ xδ: S+ −→ Γ is an S-morphism whose kernel is A(δ), so that A(δ) is a left ideal of S+. Hence A(∆) is a left ideal of S+. Further, since A(Γ) is right invariant in S we have A(Γ) is a weak ideal of S. Indeed, for any x ∈ S, s ∈ A(Γ), and γ ∈ Γ; (sx)γ = s(xγ) = sγ′ = 0Γ, where γ′ = xγ ∈ Γ, so that A(Γ)S ⊆ A(Γ). Remark 4. For γ ∈ Γ, the relation A(γ) ≡ on S+ defined by x A(γ) ≡ y if and only if xγ = yγ is a congruence on S+. Kernel of A(γ) ≡ is A(γ). Remark 5. The relation A(Γ) ≡ defined on the near-semiring S by s A(Γ) ≡ s′ if and only if sγ = s′γ for all γ ∈ Γ is a congruence on S. Moreover, A(Γ) ≡ = ⋂ γ∈Γ A(γ) ≡ so that the kernel of A(Γ) ≡ is A(Γ). Thus, by identifying A(Γ) as the kernel of canonical homomorphism from S to S/A(Γ) ≡ we have: Theorem 2. The annihilator A(Γ) of an S-semigroup Γ is an ideal of S. 2. The α-radical Let (B,+) be a commutative semigroup and let S = E + C be an affine near-semiring in which + is commutative, where E is a semiring and C is a near-semiring of constants. A pair (S, α) is called a B-pair if 1. α : (S,+) −→ (B,+) is a semigroup morphism, and 2. E ⊆ Ker α. In the following by ≡ϕ ≤ ≡ψ we mean, whenever ϕ(x) = ϕ(y) then ψ(x) = ψ(y). Consequently, ≡ϕ ≤ ≡ψ =⇒ Ker ϕ ⊆ Ker ψ. An S-semigroup Γ is said to be an (S, α)-semigroup if A(0Γ) ≡ ≤ ≡α, where ≡α is the congruence induced by the morphism α. Jo u rn al A lg eb ra D is cr et e M at h .36 Near-semirings in linear sequential machines Theorem 3. Let Γ be an (S, α)-semigroup and ≡ be a congruence of S such that ≡ ≤ A(Γ) ≡ . Then there exists an ᾱ : S/≡ −→ B such that Γ is an (S/≡, ᾱ)-semigroup. Proof. Since ≡ ≤ A(Γ) ≡ , by setting [x]γ = xγ ∀[x] ∈ S/≡, γ ∈ Γ, one can observe that it is well-defined, and consequently, Γ is S/≡-semigroup. Define ᾱ : S/≡ −→ B by ᾱ([x]) = α(x), for all [x] ∈ S/≡. Suppose [x] = [x′], i.e. x ≡ x′, then since ≡ ≤ A(Γ) ≡ and A(Γ) ≡ = ⋂ γ∈Γ A(γ) ≡ , we have ≡ ≤ A(0Γ) ≡ . Thus ≡ ≤ ≡α, so that α(x) = α(x′). Hence, ᾱ is well-defined. Moreover, ᾱ is a semigroup morphism. It is clear that S/≡ is an affine near-semiring. To show the rest of the result, i.e. (S/≡, ᾱ) forms a B-pair, it is enough to show that semiring part of S/≡ is in Ker ᾱ. If [x] is in semiring part of S/≡, then [x][0] = [0], i.e. [x0] = [0]. [x0] = [0] =⇒ x0 ≡ 0 =⇒ x0 A(Γ) ≡ 0 =⇒ (x0)γ = 0γ ∀γ ∈ Γ. In particular, (x0)0Γ = 00Γ, i.e. x0Γ = 00Γ. Which implies x A(0Γ) ≡ 0, so that α(x) = α(0). Hence, ᾱ([x]) = ᾱ([0]) as desired. Corollary 2. Let (S, α) be a B-pair and Γ an (S, α)-semigroup, then Γ is an (S/A(Γ) ≡ , ᾱ)-semigroup. Let S be a near-semiring. An S-semigroup Γ is said to be zero- generated if Γ = S0Γ. Theorem 4. If an S-semigroup Γ is zero-generated, then Γ has no proper S-subsemigroups. Proof. Suppose there exists a proper S-subsemigroup ∆ of Γ. Note that 0Γ ∈ ∆, as it is a subsemigroup of Γ. Since Γ is zero-generated, for γ ∈ Γ \ ∆, there exists s ∈ S, such that γ = s0Γ. But since ∆ is an S-subsemigroup, s0Γ ∈ ∆ for all s ∈ S. A contradiction to γ 6∈ ∆. Note that Γ = S0Γ if and only if Γ = Sc0Γ. In particular, if S = E+C, an affine near-semiring, then Γ = S0Γ if and only if Γ = C0Γ. Jo u rn al A lg eb ra D is cr et e M at h .K. V. Krishna, N. Chatterjee 37 An (S, α)-semigroup is zero-generated if it is zero-generated as S- semigroup. Given a zero-generated (S, α)-semigroup Γ we define the function ψ : Γ −→ B by ψ(γ) = α(c), where γ = c0Γ, for c ∈ C. Thus we have: Proposition 2. ψ : Γ −→ B is a semigroup morphism. Proof. Let γ = c0Γ = c′0Γ, for c, c′ ∈ C. Then c A(0Γ) ≡ c′, which implies α(c) = α(c′), as A(0Γ) ≡ ≤ ≡α. Hence ψ is well-defined, and since α is a semigroup morphism, we have ψ is a semigroup morphism. An (S, α)-semigroup Γ is said to be B-minimal if Γ is zero-generated and ≡ψ, the congruence induced by ψ, is the identity relation. Theorem 5. Let (S, α) be a B-pair and Γ an (S, α)-semigroup. Suppose ≡ is congruence of S such that ≡ ≤ A(Γ) ≡ . Then the (S/≡, ᾱ)-semigroup Γ is B-minimal if and only if the (S, α)-semigroup Γ is B-minimal. Proof. If the (S, α)-semigroup Γ is zero-generated then so is the (S/≡, ᾱ)- semigroup Γ and conversely. Also, the function ψ′ : Γ −→ B defined by ᾱ equals the function ψ : Γ −→ B defined by α. Thus, (S, α)-semigroup Γ is B-minimal if and only if it is B-minimal as an (S/≡, ᾱ)-semigroup. Now we define α-radical of a near-semiring as follows: Given a B-pair (S, α) an α-radical of S, denoted by Rα(S), is defined as the intersection of annihilators of all B-minimal (S, α)-semigroups, i.e. Rα(S) = ⋂ Γ∈B A(Γ), where B is the class of all B-minimal (S, α)-semigroups. Remark 6. Rα(S) is an ideal of the near-semiring S. Define the congruence relation Rα(S) ≡ on S by x Rα(S) ≡ y if and only if x A(Γ) ≡ y for all Γ ∈ B, so that the kernel of Rα(S) ≡ is Rα(S). Theorem 6. Let (S, α) be a B-pair and ≡ a congruence of S such that ≡ ≤ Rα(S) ≡ . Then we have Rᾱ(S/≡) ⊆ (Rα(S))/≡. Jo u rn al A lg eb ra D is cr et e M at h .38 Near-semirings in linear sequential machines Proof. Let Γ be a B-minimal (S, α)-semigroup, so that Rα(S) ⊆ A(Γ). We have seen that Γ is a B-minimal (S/≡, ᾱ)-semigroup. Let [x] ∈ S/≡ be such that [x]Γ = (0Γ) then xΓ = (0Γ) and so x ∈ A(Γ). Thus the annihilator of Γ in S/≡ is contained in A(Γ)/≡. If we write A(Γ)∗ to denote the annihilator of Γ in S/≡ then Rᾱ(S/≡) ⊆ ⋂ Γ∈B A(Γ)∗, where B is the class of B-minimal (S, α)-semigroups, and each A(Γ)∗ ⊆ A(Γ)/≡ so Rᾱ(S/≡) ⊆ ⋂ Γ∈B (A(Γ)/≡) = ( ⋂ Γ∈B A(Γ))/≡ = (Rα(S))/≡. Corollary 3. Rᾱ(S/Rα(S) ≡ ) = [0], the zero of S/Rα(S) ≡ . This is a justification for calling Rα(S) an α-radical of S. In the following we observe that α-radical is not always zero. In order to observe this, first we extend the notion of the radical J(2,0) of zero-symmetric near-semirings, introduced by van Hoorn [7], to near-semirings, then we prove that J(2,0)(S) ⊆ Rα(S) for any α. Since many examples are known where J(2,0)(S) is nonzero, it is clear that Rα(S) is not always zero. An S-semigroup Γ 6= {0Γ} is said to be essentially minimal or of type (2, 0) if SΓ 6= {0Γ} and the only S-subsemigroups of Γ are S0Γ and Γ. The radical J(2,0)(S) of a near-semiring S is defined as the intersection of the annihilators of all S-semigroups of type (2, 0). Theorem 7. Let (S, α) be a B-pair. Then J(2,0)(S) ⊆ Rα(S) for any α. Proof. From Theorem 4 one can ascertain that every B-minimal (S, α)- semigroup is essentially minimal, and so J(2,0)(S) = ⋂ Γ∈C A(Γ) ⊆ ⋂ Γ∈B A(Γ) = Rα(S), where C is the class of essentially minimal S-semigroups, and B is the class of B-minimal (S, α)-semigroups. Jo u rn al A lg eb ra D is cr et e M at h .K. V. Krishna, N. Chatterjee 39 3. Generalized linear sequential machines Let R be a semiring. A generalized linear sequential machine over R is a quintuple M = (Q,A,B, F,G), where Q,A,B are R-semimodules, F : Q×A −→ Q and G : Q×A −→ B are R-homomorphisms. In what follows M always stands for a generalized linear sequential machine (Q,A,B, F,G) over a semiring R. We call Q as the set of states, A as the input alphabet and B as the output alphabet. Let A∗, B∗ be the free monoids generated by the sets A,B, respectively. The empty word Λ will be regarded as a member of both A∗ and B∗. For x ∈ A∗, we define the function Fx : Q −→ Q, called the next state function induced by x, by FΛ(q) = q, Fxa(q) = F (Fx(q), a) for x ∈ A∗, a ∈ A. Proposition 3. For x = a1a2...an ∈ A∗, Fx = Fn0 + (Fn−1 0 q̄a1 + Fn−2 0 q̄a2 + ...+ F0q̄an−1 + q̄an), where q̄a : Q −→ Q is the constant map given by q̄a(p) = Fa(0Q) ∀p ∈ Q. Proof. We prove this result by induction on the length of the string x. Let a ∈ A and q ∈ Q. Fa(q) = F (q, a) = F (q, 0) + F (0Q, a) = F0(q) + Fa(0Q). Therefore Fa = F0 + q̄a, so that the result is true for n = 1. Assume the result is true for n = k − 1, i.e. Fa1a2...ak−1 = F k−1 0 + (F k−2 0 q̄a1 + F k−3 0 q̄a2 + ...+ F0q̄ak−2 + q̄ak−1 ). Now, Fa1a2...ak = Fak Fa1a2...ak−1 = (F0 + q̄ak )Fa1a2...ak−1 = F0Fa1a2...ak−1 + q̄ak Fa1a2...ak−1 = F0(F k−1 0 + (F k−2 0 q̄a1 + F k−3 0 q̄a2 + ...+ F0q̄ak−2 + q̄ak−1 )) + q̄ak = F k0 + F k−1 0 q̄a1 + F k−2 0 q̄a2 + ...+ F0q̄ak−1 + q̄ak . Hence the result by induction. Jo u rn al A lg eb ra D is cr et e M at h .40 Near-semirings in linear sequential machines Note that the function F0 : Q −→ Q is an R-endomorphism of Q. Thus we have: Corollary 4. For x ∈ A∗ the function Fx is an affine function of Q. The set of all affine functions of Q, Maff(Q), is a near-semiring under pointwise addition and composition of mappings (cf. Remark 3). Con- sider the syntactic monoid M of M, i.e. M = {Fx \| x ∈ A∗}, a submonoid of Maff(Q). Note that Md = {Fn0 \| n ≥ 1}, the endomorphism part of M . Proposition 4. MdM ⊆M . Proof. Let Fn0 ∈ Md and Fx ∈ M with x = a1a2 . . . ak. Choose y = a1a2 . . . ak n times ︷︸︸︷ 00 . . . 0 ∈ A∗. Then by Proposition 3, Fy = Fn+k 0 + (Fn+k−1 0 q̄a1 + Fn+k−2 0 q̄a2 + ...+ Fn+1 0 q̄an−1 + Fn0 q̄an +Fn−1 0 q̄0 + Fn−2 0 q̄0 + . . .+ q̄0) = Fn+k 0 + (Fn+k−1 0 q̄a1 + Fn+k−2 0 q̄a2 + ...+ Fn+1 0 q̄an−1 + Fn0 q̄an) = Fn0 (F k0 + (F k−1 0 q̄a1 + F k−2 0 q̄a2 + ...+ F0q̄an−1 + q̄an)) = Fn0 Fx. Thus, for any n ≥ 1 and x ∈ A∗, Fn0 Fx ∈M . The subnear-semiring of Maff(Q), generated by M is defined as the syntactic near-semiring of M, denoted by SM. Remark 7. 1. Every nonzero element of SM can be written as n∑ i=1 mi for mi ∈M (cf. Propositions 1 and 4). 2. The state set Q of M is an S-semigroup with S = SM. 3. SM is an affine near-semiring. For q ∈ Q, the sequential function defined by q, fq : A∗ −→ B∗ is defined inductively as fq(Λ) = Λ, fq(a) = G(q, a), fq(xa) = fq(x)fFx(q)(a) for x ∈ A∗, a ∈ A. Jo u rn al A lg eb ra D is cr et e M at h .K. V. Krishna, N. Chatterjee 41 For a ∈ A and q ∈ Q note that fq(a) = G(q, a) = G(q, 0) +G(0Q, a) = G0(q) +Ga(0Q), by adapting the notation of the state function Fx. Let M = (Q,A,B, F,G) and M′ = (Q′, A,B, F ′, G′) be generalized linear sequential machines. A generalized linear sequential machine mor- phism, denoted by ϕ : M −→ M′, is an R-homomorphism ϕ : Q −→ Q′ such that ϕ(Fa(q)) = F ′ a(ϕ(q)), Ga(q) = G′ a(ϕ(q)) for q ∈ Q, a ∈ A. Remark 8. For x ∈ A∗, ϕ(Fx(q)) = F ′ x(ϕ(q)). The following result establishes the interrelation between M and SM. Theorem 8. If ϕ : M −→ M′ is a surjective generalized linear sequential machine morphism, then there exists a near-semiring homomorphism ψ : SM −→ SM′ such that, for q ∈ Q, s ∈ SM, ϕ(sq) = ψ(s)(ϕ(q)). Furthermore, for q ∈ Q, fq = f ′ ϕ(q). Proof. Let M and M ′ be the syntactic monoids of M and M′ respectively. By a standard result in automata theory, there exists a monoid morphism η : M −→ M ′ such that ϕ(mq) = η(m)ϕ(q) for q ∈ Q,m ∈ M. Define a zero fixing mapping ψ : SM −→ SM′ by ψ( k∑ i=1 mi) = k∑ i=1 η(mi), for mi ∈M. For mi,m ′ j ∈ M , assume k∑ i=1 mi = l∑ j=1 m′ j . That means, they are equal at every point of Q. By applying the morphism ϕ, we will arrive at ( k∑ i=1 η(mi))(ϕ(q)) = ( l∑ j=1 η(m′ j))(ϕ(q)) for all q ∈ Q. But since ϕ is surjective, we get k∑ i=1 η(mi) = l∑ j=1 η(m′ j). Thus, ψ is well-defined. Also, it can be easily observed that ψ is a near-semiring homomorphism. Jo u rn al A lg eb ra D is cr et e M at h .42 Near-semirings in linear sequential machines For q ∈ Q, s = k∑ i=1 mi ∈ SM, we have ϕ(sq) = ϕ( k∑ i=1 miq) = k∑ i=1 ϕ(miq) = k∑ i=1 η(mi)(ϕ(q)) = ( k∑ i=1 η(mi) ) (ϕ(q)) = ψ(s)(ϕ(q)). Now we show by an induced argument that for q ∈ Q, f ′ ϕ(q) = fq. For a ∈ A, fq(a) = Ga(q) = G′ a(ϕ(q)) = f ′ ϕ(q)(a). Further, for x ∈ A∗; a ∈ A, fq(xa) = fq(x)fFx(q)(a) = f ′ϕ(q)(x)f ′ ϕ(Fx(q))(a) = f ′ϕ(q)(x)f ′ F ′ x(ϕ(q))(a), by Remark 8 = f ′ϕ(q)(xa). Thus fq(x) = f ′ ϕ(q)(x) for all x ∈ A∗. In the following we discuss the role of syntactic near-semiring SM in the minimization of M. Define the relation ∼ on Q by q ∼ q′ if and only if G0F n 0 (q) = G0F n 0 (q′) for all n ≥ 0. Theorem 9. For q, q′ ∈ Q, if q ∼ q′ then fq = fq′ . Proof. We prove this by induction on length of x ∈ A∗. Since fq(a) = G0(q) +Ga(0Q); fq′(a) = G0(q ′) +Ga(0Q); and G0(q) = G0(q ′) from the hypothesis, we have fq(a) = fq′(a) for all a ∈ A. If fq(x) = fq′(x), where x = a1a2 . . . an, then fq(xa) = fq(x)fFx(q)(a), and fFx(q)(a) = G(Fx(q), a) = G0(Fx(q)) +Ga(0Q) = G0(F n 0 (q) + n∑ i=1 Fn−i0 q̄ai (q)) +Ga(0Q) = G0F n 0 (q) + n∑ i=1 G0F n−i 0 (qai ) +Ga(0Q). Similarly, fFx(q)(a) = G0F n 0 (q′) + n∑ i=1 G0F n−i 0 (qai ) +Ga(0Q), Jo u rn al A lg eb ra D is cr et e M at h .K. V. Krishna, N. Chatterjee 43 so that fq(xa) = fq(x)fFx(q)(a) = fq′(x)fFx(q′)(a) = fq′(xa). Theorem 10. The relation ∼ is a congruence relation on Q. Proof. Since Fn0 : Q −→ Q is a composition of R-homomorphism F0 with itself for n times, we have Fn0 is an R-homomorphism ∀n. Also, since G0 : Q −→ B is an R-homomorphism, we get G0F n 0 : Q −→ B an R-homomorphism ∀n. Hence the relation ∼ is a congruence on Q, as it is the intersection of induced congruences of G0F n 0 for all n. A machine M is said to be reduced if the relation ∼ defined on Q is trivial, i.e. q ∼ q′ =⇒ q = q′ for all q, q′ ∈ Q. Thus we have: Corollary 5. The generalized linear sequential machine Mr = (Q′, A,B, F ′, G′) is a reduced machine of M, where Q′ = Q/ ∼, F ′([q], a) = [F (q, a)], and G′([q], a) = [G(q, a)], for all q ∈ Q, a ∈ A. As in Eilenberg’s work [1], we assume 0Q ∈ Q to be the initial state of M. A generalized linear sequential machine M = (Q,A,B, F,G) is called accessible if given any q ∈ Q there exists x ∈ A∗ such that Fx(0Q) = q, i.e. any state is reachable from the initial state 0Q. Remark 9. If M is accessible then the S-semigroup Q is zero generated, i.e. SM0Q ⊇M0Q = Q. Consequently, the S-semigroup Q has no proper S-subsemigroups. A generalized linear sequential machine M is called minimal if it is accessible and reduced. In the following section we obtain a necessary condition to test the minimality of M using an α-radical of SM. 4. The radical applied to machines Assume that M = (Q,A,B, F,G) is a generalized linear sequential ma- chine over a semiring R. Let S = SM be the syntactic near-semiring of M. We have observed that S is an affine near-semiring, say S = E + C, and Q an S-semigroup. Furthermore, G defines an R-homomorphism G0 : Q −→ B. Define α : S −→ B by α(s) = G0(s0Q) ∀s ∈ S. Jo u rn al A lg eb ra D is cr et e M at h .44 Near-semirings in linear sequential machines Note that, α is a semigroup morphism and α(e) = G0(e0Q) = G0(0Q) = 0 ∀e ∈ E, so that (S, α) is B-pair. Moreover, Q is an (S, α)-semigroup, because ∀s, t ∈ S, s A(0Q) ≡ t =⇒ s0Q = t0Q =⇒ G0(s0Q) = G0(t0Q) =⇒ α(s) = α(t) =⇒ s ≡α t. Now we examine the α-radical Rα(S), which is the intersection of anni- hilators of all B-minimal (S, α)-semigroups. If M is minimal, then the state set Q, which is an (S, α)-semigroup, is zero-generated and the equivalence relation ∼ is trivial. Consequently, Q is B-minimal. But the annihilator of Q, A(Q) = {s ∈ S \| sq = 0 ∀q ∈ Q} = {s ∈ S \| s = 0} = (0) so that the α-radical of S, Rα(S) = ⋂ Γ∈B A(Γ) ⊆ A(Q) = (0), where B is the class of B-minimal (S, α)-semigroups. Thus Rα(S) = (0). This can be summarized as follows: Theorem 11. If M is minimal then Rα(S) = (0). The converse of Theorem 11 is not necessarily true, as there exist non-minimal machines with a zero radical [5]. Acknowledgements We are very much thankful to the referee for his/her valuable comments to improve certain parts of the paper. References [1] S. Eilenberg, Automata, Languages, and Machines, Vol. A, Academic Press, New York, 1974. [2] Jonathan S. Golan, Semirings and Their Applications, Kluwer Academic Publish- ers, Dordrecht, 1999. [3] George Grätzer, Universal Algebra, Second Edition, Springer-Verlag, New York, 1979. [4] M. Holcombe, The Syntactic Near-Ring of a Linear Sequential Machine, Proc. Edinburgh Math. Soc.(2), 26(1) (1983), pp. 15–24. Jo u rn al A lg eb ra D is cr et e M at h .K. V. Krishna, N. Chatterjee 45 [5] M. Holcombe, A Radical for Linear Sequential Machines, Proc. Roy. Irish Acad. Sect. A, 84(1) (1984), pp. 27–35. [6] Willy G. van Hoorn, B. van Rootselaar, Fundamental Notions in the Theory of Seminearrings, Compositio Math., 18 (1967), pp. 65–78. [7] Willy G. van Hoorn, Some Generalisations of the Jacobson Radical for Semi- Nearrings and Semirings, Math. Z., 118 (1970), pp. 69–82. Contact information K. V. Krishna Department of Mathematics Indian Institute of Technology Delhi Hauz Khas, New Delhi - 110 016, India E-Mail: kv.krishna@member.ams.org N. Chatterjee Department of Mathematics Indian Institute of Technology Delhi Hauz Khas, New Delhi - 110 016, India E-Mail: niladri@maths.iitd.ac.in Received by the editors: 25.03.2005 and final form in 20.10.2005.

A necessary condition to test the minimality of generalized linear sequential machines using the theory of near-semirings

Репозитарії

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