E:\UZIV\SARKA\Clanky\RM_26\FINAL\RM_26_4.dvi RATIO MATHEMATICA 26 (2014), 65–76 ISSN:1592-7415 Recognizability in Stochastic Monoids A. Kalampakasa, O. Louscou-Bozapalidoub, S. Spartalisc a,cDepartment of Production Engineering and Management, Democritus University of Thrace, 67100, Xanthi, Greece bSection of Mathematics and Informatics, Technical Institute of West Macedonia, 50100, Kozani, Greece akalampakas@gmail.duth.gr sspar@pme.duth.gr Abstract Stochastic monoids and stochastic congruences are introduced and the syntactic stochastic monoid ML associated to a subset L of a stochastic monoid M is constructed. It is shown that ML is mini- mal among all stochastic epimorphisms h : M → M ′ whose kernel saturates L. The subset L is said to be stochastically recognizable whenever ML is finite. The so obtained class is closed under boolean operations and inverse morphisms. Key words: recognizability, stochastic monoids, minimization. MSC 2010: 68R01, 68Q10, 20M32. 1 Introduction A stochastic subset of a set M is a function F : M → [0, 1] with the additional property Σm∈M F (m) = 1, i.e., F is a discrete probability distri- bution. The corresponding class is denoted by Stoc(M). Our subject of study, in the present paper, are stochastic monoids which were introduced in [4]. A stochastic monoid is a set M equipped with a stochastic multiplication M × M → Stoc(M) which is associative and unitary. It can be viewed as a nondeterministic monoid (cf. [1, 2, 3]) with multiplication M ×M →P(M) such that for all m1, m2 ∈ M a discrete probability distribution is assigned on the set m1 · m2. 65 Kalampakas, Louscou-Bozapalidou, Spartalis A congruence on a stochastic monoid M is an equivalence ∼ on M such that m1 ∼ m ′ 1 and m2 ∼ m ′ 2 imply ∑ n∈C (m1 · m2)(n) = ∑ n∈C (m′1 · m ′ 2)(n) for all ∼-classes C. The quotient M/ ∼ admits a stochastic monoid structure rendering the canonical function m 7→ [m] an epimorphism of stochastic monoids. The classical Isomorphism Theorem of Algebra still holds in the stochastic setup, namely for any epimorphism of stochastic monoids h : M → M ′ and every stochastic congruence ∼ on M ′ its inverse image h−1(∼) defined by m1h −1(∼)m2 iff h(m1) ∼ h(m2), is again a stochastic congruence and the quotient stochastic monoids M/h−1(∼) and M ′/ ∼ are isomorphic. In particular if ∼ is the equality, then h−1(=) is the kernel congruence of h (denoted by ∼h) m1 ∼h m2 iff h(m1) = h(m2), and the stochastic monoids M/ ∼h and M ′ are isomorphic. We show that stochastic congruences are closed under the join operation. This allows us to construct the greatest stochastic congruence included in an equivalence ∼. It is the join of all stochastic congruences on M included into ∼ and it is denoted by ∼stoc. The quotient stochastic monoid M/ ∼stoc is denoted by M stoc and has the following universal property: given an epimorphism of stochastic monoids h : M → M ′ whose kernel ∼h saturates the equivalence ∼ there exists a unique epimorphism of stochastic monoids h′ : M ′ → M stoc such that h′ ◦ h = hstoc, where hstoc : M → M stoc is the canonical epimorphism into the quotient. This result states that hstoc is minimal among all epimorphisms saturating ∼. Let M be a stochastic monoid and L ⊆ M. Denote by ∼L the greatest congruence of M included in the partition (equivalence) {L, M − L}, i.e., ∼L= {L, M − L} stoc. The quotient stochastic monoid ML = M/ ∼L will be called the syntactic stochastic monoid of L and it is characterized by the following universal property. For every stochastic monoid M and every epimorphism h : M → M ′ verifying h−1(h(L)) = L, there exists a unique epimorphism h′ : M ′ → ML such that h ′ ◦ h = hL where hL : M → ML is the canonical projection into the quotient. 66 Recognizability in Stochastic Monoids A subset L of a stochastic monoid M is stochastically recognizable if there exist a finite stochastic monoid M ′ and a morphism h : M → M ′ such that h−1(h(L)) = L. By taking into account the previous result we get that L is recognizable if and only if its syntactic stochastic monoid is finite. Moreover stochastically recognizable subsets are closed under boolean operations and inverse morphisms. 2 Stochastic Subsets Some useful elementary facts are displayed. Let (xi)i∈I , (xij )i∈I,j∈J , (yj)j∈J be families of nonnegative reals, then sup i∈I,j∈J xij = sup i∈I sup j∈J xij = sup j∈J sup i∈I xij , sup i∈I,j∈J xiyj = sup i∈I xi · sup j∈J yj, provided that the above suprema exist. If sup I′⊆f inI Σi∈I′ xi exists, then we say that the sum Σi∈I xi exists and we put Σ i∈I xi = sup I′⊆f inI Σ i∈I′ xi where the notation I′ ⊆f in I means that I ′ is a finite subset of I. It holds ∑ i∈I,j∈J xij = ∑ i∈I ∑ j∈J xij = ∑ j∈J ∑ i∈I xij , ∑ i∈I,j∈J xiyj = ∑ i∈I xi ∑ j∈J yj. Let M be a non empty set and [0, 1] the unit interval, a stochastic subset of M is a function F : M → [0, 1] with the additional property that the sum of its values exists and is equal to 1 ∑ m∈M F (m) = 1. We denote by Stoc(M) the set of all stochastic subsets of M. Let Fi : M → R+, i ∈ I, be a family of functions such that for every m ∈ M the sum ∑ i∈I Fi(m) exists. Then the assignment m 7→ ∑ i∈I Fi(m) defines a function from M to R+ denoted by ∑ i∈I Fi, i.e., ( ∑ i∈I Fi ) (m) = ∑ i∈I Fi(m), m ∈ M. 67 Kalampakas, Louscou-Bozapalidou, Spartalis Now let (λi)i∈I be a family in [0, 1] such that ∑ i∈I λi = 1 and Fi ∈ Stoc(M), i ∈ I. For any finite subset I′ of I and any m ∈ M, we have ∑ i∈I λiFi(m) = sup I′⊆f inI ∑ i∈I′ λiFi(m) ≤ 1. Thus ∑ i∈I λiFi is defined and belongs to Stoc(M) because ∑ m∈M ( ∑ i∈I λiFi ) (m) = ∑ m∈M ∑ i∈I λiFi(m) = ∑ i∈I ∑ m∈M λiFi(m) = ( ∑ i∈I λi ) ( ∑ m∈M Fi(m)) = 1 · 1 = 1. Thus we can state: Strong Convexity Lemma (SCL). The set Stoc(M) is a strongly convex set, i.e., for any stochastic family λi ∈ [0, 1], Fi ∈ Stoc(M), i ∈ I the function ∑ i∈I λiFi is in Stoc(M). For arbitrary sets M, M ′ any function h : M → Stoc(M ′) can be extended into a function h̄ : Stoc(M) → Stoc(M ′) by setting h̄(F ) = ∑ m∈M F (m) · h(m). In particular, any function h : M → M ′ is extended into a function h̄ : Stoc(M) → Stoc(M ′) by the same as above formula. This formula is legiti- mate since by the strong convexity lemma ∑ m∈M F (m) = 1 and h(m) is a stochastic subset of M. Hence, for any stochastic subset F : M → [0, 1] we have the expansion formula F = ∑ m∈M F (m)m̂ where m̂ : M → [0, 1] stands for the singleton function m̂(n) = { 1, if n = m; 0, if n 6= m. Often m̂ is identified with m itself. 68 Recognizability in Stochastic Monoids 3 Stochastic Congruences Our main interest is focused on equivalences in the stochastic setup. Any equivalence relation ∼ on the set M, can be extended into an equivalence relation ≈ on the set Stoc(M) as follows: for F, F ′ ∈ Stoc(M) we set F ≈ F ′ if and only if for each ∼-class C it holds ∑ m∈C F (m) = ∑ m∈C F ′(m), that is both F, F ′ behave stochastically on C in similar way. The above sums exist because F, F ′ are stochastic subsets of M: ∑ m∈C F (m) ≤ ∑ m∈M F (m) = 1. The equivalence ≈ has a fundamental property, it is compatible with strong convex combinations. Proposition 3.1. Assume that (λi)i∈I is a stochastic family of numbers in [0, 1] and Fi, F ′ i ∈ Stoc(M), for all i ∈ I. Then Fi ≈ F ′ i , for all i ∈ I, implies ∑ i∈I λiFi ≈ ∑ i∈I λiF ′ i . Proof. By hypothesis we have ∑ m∈C Fi(m) = ∑ m∈C F ′i (m) for any ∼-class C in M, and thus ∑ m∈C ( ∑ i∈I λiFi ) (m) = ∑ m∈C ∑ i∈I λiFi(m) = ∑ i∈I λi ∑ m∈C Fi(m) = ∑ i∈I λi ∑ m∈C F ′i (m) = ∑ m∈C ∑ i∈I λiF ′ i (m) = ∑ m∈C ( ∑ i∈I λiF ′ i ) (m) that is ∑ i∈I λiFi ≈ ∑ i∈I λiF ′ i as wanted. 69 Kalampakas, Louscou-Bozapalidou, Spartalis 4 Stochastic Monoids A stochastic monoid is a set M equipped with a stochastic multiplication, i.e. a function M × M → Stoc(M), (m1, m2) 7→ m1m2 which is associative ∑ n∈M (m1m2)(n)(nm3) = ∑ n∈M (m2m3)(n)(m1n) and unitary i.e. there is an element e ∈ M such that me = m = em, for all m ∈ M. For instance any ordinary monoid can be viewed as a stochastic monoid. In the present study it is important to have a congruence notion. More precisely, let M be a stochastic monoid and ∼ an equivalence relation on the set M, such that: m1 ∼ m ′ 1 and m2 ∼ m ′ 2 implies ∑ m∈C (m1m2)(m) = ∑ m∈C (m′1m ′ 2)(m) for all ∼-classes C, then ∼ is called a stochastic congruence on M. This condition can be reformulated as follows: m1 ∼ m ′ 1 and m2 ∼ m ′ 2 implies m1m2 ≈ m ′ 1m ′ 2. Proposition 4.1. The quotient set M/ ∼ is structured into a stochastic monoid by defining the stochastic multiplication via the formula ([m1][m2])([n]) = ∑ m∈[n] (m1m2)(m). Proof. First observe that the above multiplication is well defined. Next for every ∼-class [b] we have (([m1][m2]) [m3]) ([b]) = ∑ [n]∈M/∼ ([m1][m2])([n])([n][m3])([b]) = ∑ [n]∈M/∼ ∑ n1∈[n] (m1m2)(n1) ∑ b′∈[b] (nm3)(b ′) 70 Recognizability in Stochastic Monoids Since n ∼ n1 we get = ∑ [n]∈M/∼ ∑ n1∈[n] (m1m2)(n1) ∑ b′∈[b] (n1m3)(b ′) = ∑ [n]∈M/∼ ∑ b′∈[b] ∑ n1∈[n] (m1m2)(n1)(n1m3)(b ′) = ∑ b′∈[b] ∑ n1∈M (m1m2)(n1)(n1m3)(b ′). By taking into account the associativity of M we obtain: = ∑ b′∈[b] ∑ n1∈M (m2m3)(n1)(m1n1)(b ′) = ([m1]([m2][m3]))([b]). Congruences on an ordinary monoid M coincide with stochastic congru- ences when M is viewed as a stochastic monoid. The first question arising is whether stochastic congruence is a good algebraic notion. This is checked by the validity of the known isomorphism theorems in their stochastic variant. Given stochastic monoids M and M ′, a strict morphism from M to M ′ is a function h : M → M ′ preserving stochastic multiplication and units, i.e., h̄(m1m2) = h(m1)h(m2), h(e) = e ′, for all m1, m2 ∈ M, where e, e ′ are the units of M, M ′ respectively, and h̄ : Stoc(M) → Stoc(M ′) the canonical extension of h defined in Section 2. Theorem 4.1. Given an epimorphism of stochastic monoids h : M → M ′ and a stochastic congruence ∼ on M ′, its inverse image h−1(∼) defined by m1h −1(∼)m2 if h(m1) ∼ h(m2) is also a stochastic congruence and the stochastic quotient monoids M/h−1(∼ ) and M ′/ ∼ are isomorphic. Proof. Assume that m1h −1(∼)m′1 and m2h −1(∼)m′2 that is h(m1) ∼ h(m ′ 1) and h(m2) ∼ h(m ′ 2). 71 Kalampakas, Louscou-Bozapalidou, Spartalis Then h̄(m1m2) = h(m1)h(m2) ≈ h(m ′ 1)h(m ′ 2) = h̄(m ′ 1m ′ 2), that is for all C ∈ M ′/ ∼, we have ∑ c∈C h̄(m1m2)(c) = ∑ c∈C h̄(m′1m ′ 2)(c), but ∑ c∈C h̄(m1m2)(c) = ∑ c∈C ∑ m∈M (m1m2)(m)h(m)(c) = ∑ m∈M (m1m2)(m) ∑ c∈C h(m)(c) = ∑ m∈h−1(C) (m1m2)(m). Recall that all h−1(∼)-classes are of the form h−1(C), C ∈ M ′/ ∼. Conse- quently, = ∑ m∈h−1(C) (m1m2)(m) = ∑ m∈h−1(C) (m′1m ′ 2)(m) which shows that h−1(∼) is indeed a congruence of the stochastic monoid M. The desired isomorphism ĥ : M/h−1(∼) → M ′/ ∼ is given by ĥ([m]h−1(∼)) = [h(m)]∼. Corolary 4.1. Let h : M → M ′ be an epimorphism of stochastic monoids. Then the kernel equivalence m1 ∼h m2 if h(m1) = h(m2) is a congruence on M and the stochastic quotient monoid M/ ∼h is isomor- phic to M ′. Given stochastic monoids M1, . . . , Mk the stochastic multiplication [(m1, . . . , mk) · (m ′ 1, . . . , m ′ k)](n1, · · · , nk) = (m1m ′ 1)(n1) · · ·(mkm ′ k)(nk) structures the set M1×·· ·×Mk into a stochastic monoid so that the canonical projection πi : M1 ×·· ·× Mk → Mi, πi(m1, . . . , mk) = mi becomes a morphism of stochastic monoids. Notice that the above multipli- cation is stochastic because ∑ ni∈Mi 1≤i≤k (m1m ′ 1)(n1) · · ·(mkm ′ k)(nk) = ∑ n1∈M1 (m1m ′ 1)(n1) · · · ∑ nk∈Mk (mkm ′ k)(nk) = 1 · · ·1 = 1. 72 Recognizability in Stochastic Monoids Theorem 4.2. Let ∼i be a stochastic congruence on the stochastic monoid Mi (1 ≤ i ≤ k). Then ∼1 ×·· ·× ∼k is a stochastic congruence on the stochastic monoid M1×·· ·×Mk and the stochastic monoids M1×·· ·×Mk/ ∼1 ×·· ·×∼k and M1/ ∼1 ×·· ·× Mk/ ∼k are isomorphic. 5 Greatest Stochastic Congruence Saturat- ing an Equivalence First observe that, due to the symmetric property which an equivalence relation satisfies, the sumability condition in the definition of a congruence can be replaced by the weaker condition: m1 ∼ m ′ 1 and m2 ∼ m ′ 2 implies ∑ m∈C (m1m2)(m) ≤ ∑ m∈C (m′1m ′ 2)(m) for all ∼-classes C. Lemma 5.1. The equivalence ∼ on the stochastic monoid M is a congruence if and only if the following condition is fulfilled: m ∼ m′, implies ∑ b∈C (m · n)(b) ≤ ∑ b∈C (m′ · n)(b) and ∑ b∈C (n · m)(b) ≤ ∑ b∈C (n · m′)(b). Proof. One direction is immediate whereas for the opposite direction we have: m1 ∼ m ′ 1 and m2 ∼ m ′ 2 imply ∑ b∈C (m1 · m2)(b) ≤ ∑ b∈C (m′1 · m2)(b) ≤ ∑ b∈C (m′1 · m ′ 2)(b). Next we demonstrate that stochastic congruences are closed under the join operation. We recall that the join ∨ i∈I ∼i of a family of equivalences (∼i)i∈I on a set A is the reflexive and transitive closure of their union: ∨ i∈I ∼i= ( ⋃ i∈I ∼i )∗ . Theorem 5.1. If (∼i)i∈I is a family of stochastic congruences on M, then their join ∨ i∈I ∼i is also a stochastic congruence. Proof. Let ∼1,∼2 be two congruences on M and ∼=∼1 ∨∼2. First we show that m ∼1 m ′ implies ∑ b∈C (m · n)(b) ≤ ∑ b∈C (m′ · n)(b), 73 Kalampakas, Louscou-Bozapalidou, Spartalis for all ∼-classes C. From the inclusion ∼1⊆∼ we get that C is the disjoint union C = m ⋃ j=1 C1j where C1j denote ∼1-classes. Then ∑ b∈C (m · n)(b) = m ∑ j=1 ∑ b∈C1 j (m · n)(b) ≤ m ∑ j=1 ∑ b∈C1 j (m′ · n)(b) = ∑ b∈C (m′ · n)(b). By a similar argument we show that m ∼2 m ′ implies ∑ b∈C (m · n)(b) ≤ ∑ b∈C (m′ · n)(b), for all ∼-classes C. Now, if m ∼ m′, without any loss we may assume that m ∼1 m1 ∼2 m2 ∼1 · · · ∼1 m2λ−1 ∼2 m ′ for some elements m1, . . . , m2λ−1 ∈ M. Applying successively the previous facts, we obtain ∑ b∈C (m · n)(b) ≤ ∑ b∈C (m1 · n)(b) ≤ ·· ·≤ ∑ b∈C (m2λ−1 · n)(b) ≤ ∑ b∈C (m′ · n)(b). For an arbitrary set of congruences we proceed in a similar way. The previous result leads us to introduce the greatest stochastic congru- ence included into an equivalence ∼ of M. It is the join of all stochastic congruences on M included into ∼ and it is denoted by ∼stoc. The quo- tient stochastic monoid M/ ∼stoc is denoted by M stoc and has the following universal property Theorem 5.2. Given an epimorphism of stochastic monoids h : M → M ′ whose kernel ∼h saturates the equivalence ∼ there exists a unique epimor- phism of stochastic monoids h′ : M ′ → M stoc rendering commutative the triangle M stocM ′ h′ M h hstoc 74 Recognizability in Stochastic Monoids where hstoc : M → M stoc is the canonical projection m 7→ [m]stoc sending every element m ∈ M on its ∼stoc-class. Proof. By virtue of the Isomorphism Theorem the stochastic monoid M ′ is isomorphic to the quotient M/ ∼h. Since by assumption ∼h⊆∼ stoc, h′ is the following composition M ′ ∼ → M/ ∼h f → M/ ∼stoc= M stoc, with f ([m]h) = [m]stoc, [m]h being the ∼h-class of m. The previous result states that hstoc is minimal among all epimorphisms saturating ∼. 6 Syntactic Stochastic Monoids Let M be a stochastic monoid and L ⊆ M. Denote by ∼L the greatest congruence of M included in the partition (equivalence) {L, M − L}, i.e., ∼L= {L, M − L} stoc. The quotient stochastic monoid ML = M/ ∼L will be called the syntactic stochastic monoid of L and it is characterized by the following universal property. Theorem 6.1. For every stochastic monoid M and every epimorphism h : M → M ′ verifying h−1(h(L)) = L, there exists a unique epimorphism h′ : M ′ → ML rendering commutative the triangle MLM ′ h′ M h hL where hL is the canonical morphism sending every element m ∈ M to its ∼L-class. Proof. The hypothesis h−1(h(L)) = L means that ∼h saturates L and so the statement follows immediately by Theorem 5.2. Given stochastic monoids M, M ′ we write M ′ < M if there is a stochastic monoid M̄ and a situation 75 Kalampakas, Louscou-Bozapalidou, Spartalis M ′ h ←− M̄ i −→ M where i (resp. h) is a monomorphism (resp. epimorphism). Theorem 6.2. Given subsets L1, L2, L of a stochastic monoid M it holds i) ML1∩L2 < ML1 × ML2 , ii) ML = ML̄, where L̄ designates the set theoretic complement of L, iii) ML1∪L2 < ML1 × ML2 , iv) If h : M → N is an epimorphism of ND-monoids and L ⊆ N, then Mh−1(L) = ML. Proof. The proof follows by applying Theorem 6.1. A subset L of a stochastic monoid M is stochastically recognizable if there exist a finite stochastic monoid M ′ and a morphism h : M → M ′ such that h−1(h(L)) = L. The class of stochastically recognizable subsets of M is denoted by StocRec(M). By taking into account Theorem 6.1 we get Proposition 6.1. L ⊆ M is recognizable if and only if its syntactic stochastic monoid is finite, card(ML) < ∞. Putting this result together with Theorem 6.2 we yield Proposition 6.2. The class StocRec(M) is closed under boolean operations and inverse morphisms. References [1] I.P. Cabrera, P. Cordero, M. Ojeda-Aciego, Non-deterministic Algebraic Structures for Soft Computing, Advances in Computational Intelligence, Lecture Notes in Computer Science 6692(2011) 437-444. [2] J. S. Golan, Semirings of Formal Series over Hypermonoids: Some In- teresting Cases, Kyungpook Math. J. 36(1996) 107-111. [3] A. Kalampakas and O. Louskou-Bozapalidou, Syntactic Nondeterminis- tic Monoids, submitted in Pure Mathematics and Applications. [4] O. Louskou-Bozapalidou, Stochastic Monoids, Applied Mathematical Sciences 3(2007) 443-446. 76