# Reducing Computational Overhead by Improving the CRI and IRI Implication Step

Authors: Thoai Phu Vo; Joy Iong-Zong Chen
Journal: Journal of Control Science and Engineering
 (2015)

---

## Abstract

In conventional SISO fuzzy expert systems (n-element input, m-element output), the implication step requires the O(n×m) operations using compositional rule-based inference (CRI) and individual rule-based inference (IRI). However, this introduces excessive complexity. This paper proposes two methods, sort compositional rule-based inference (SCRI) and sort individual rule-based inference (SIRI) aiming at reducing both temporal and spatial complexity by changing the operation of the implication step to O((n+m)log2(n+m)). We also propose a divide-and-conquer technique, called Quicksort, to verify the accuracy of SCRI and SIRI algorithms deployment to easily outperform the CRI and IRI methods.


---

## Body

## 1. Introduction

The inference compositional rule (CRI) was first proposed by Zadeh [1] to solve the fuzzy modus ponens (FMP) and fuzzy modus tollens (FMT) models. Later Dubois and Prade [2] introduced two approaches to present the inference of a set of parallel rules for solving the local inference approach, known as IRI, and the global inference approach, which is known as CRI. Many researches have been conducted on CRI and IRI. The first topic is “aggregation operator” [3] introducing two methods to deal with aggregation operator issues. The first infer then aggregate (FITA) is known as IRI, and the first aggregate then infer (FATI) is known as CRI. They attempt to find an operator for CRI and IRI aggregation. Assilian [4] used the max-min method. A “min” operator is selected as a conjunction in the rule premise and the implication function while a “max” operator is used for aggregation. Dubois [5] used a “min” operator for aggregation in decision-making. To reduce the computational time, the authors [6, 7] replaced a MISO fuzzy rule with an equivalent collection of SISO rules with two kinds of aggregation operators.The second topic involves fuzzy logic application in many fields using the CRI method, the second topic. Mamdani [8] applied fuzzy logic in designing controllers for industrial plants. Reference [9] applied an adaptive fuzzy inference scheme to stock data and showed that the adaptive fuzzy rule-based schemes provide clean decision to buy, hold, and sale. Reference [10] proposed a fuzzy interval reasoning (FIR) and [11] introduced a fuzzy logic controller to serve web shopping. The third topic is new algorithms based on the CRI context. Reference [12] presented a new feedback method based on CRI (FBCRI) to improve the robustness of CRI fuzzy reasoning methods. Reference [13] introduced a CMI (compatibility modification inference), which is reduced by CRI. References [14–21] developed the Triple I method, based on CRI imperfections. Accordingly, [14] proposed the full implication Triple I method (a hybrid method based on implication and composition), designed as a supplement for the CRI method. Reference [15] proposed the Triple I FMP and FMT for generalized α-triple I method. An investigation into a formalized Triple I method is reported in [16] where the authors tried to set a sound logical foundation for the unified TI algorithms. Accordingly, other researchers developed new implications, the fourth topic. Reference [22] proposed a new implication: “nilpotent minimum implication.”Other researchers studied Mamdani and Sugeno type fuzzy model applications, the fifth topic. Reference [23] showed the advantage of Sugeno type fuzzy inference system in that it can be integrated with neural networks and genetic algorithms or other optimization techniques. In [24] the Mamdani and Sugeno models are used to compute the resonant frequency of rectangular microstrip antennas (MSAs) with thin and thick substrates. Finally, [25] implemented a supervised learning method based on membership function training in the Mamdani fuzzy model context. Specifically, the autozoom function of a digital camera is modeled adopting the Mamdani technique.We have shown five research topics to view that the improvement of CRI and IRI has never been done. SCRI and SIRI are used to reduce the computational time and space complexity of CRI and IRI in this research. Suppose that there arer rules in a fuzzy expert system rule base and they are defined as (1)IfxisAk,thenyisBk,where Ak and Bk,k=1,2,…,r, are fuzzy sets defined in the universe of discourses V and W, respectively.Two basic methods are used to obtain a meaningful inference for a given observationA′. The first method, CRI, includes three steps: (1) implication, (2) aggregation, and (3) composition. The second method, IRI, includes three steps: (1) implication, (2) composition, and (3) aggregation. The two methods include the same implication step, which includes two substeps: cylindrical extension and calculating relational matrix using a space of O(n×m) and an operation of O(n×m). The main contributions of this paper are as follows.(i)
This paper clearly showed the advantages of CRI comparing to IRI in SISO fuzzy system.(ii)
This paper proposes two methods, sort compositional rule-based inference (SCRI) and sort individual rule-based inference (SIRI), aiming at reducing the operation of the implication step fromO(n×m) to O((n+m)log2(n+m)).


## 2. Multiple Fuzzy Reasoning Schemes

### 2.1. Quicksort

This study adopted a method referred to as Quicksort, a divide-and-conquer method, which proceeds through four steps: (1) arbitrarily select an element in the array (the pivot), (2) divide the array into two subarrays of uneven size (the partition phase), (3) sort the subarrays recursively, and (4) position the pivot between the two sorted subarrays to obtain the final sorted array. The Quicksort performance depends on the pivot elements in the array, as outlined below.


#### 2.1.1. The Worst Case

The worst case scenario occurs when the pivot element is the largest or smallest element in the array. In Figure1, the pivot element is the smallest element in the array. The total number C(l) of comparisons performed by Quicksort in sorting an array of size l is calculated as (2)Cl=l+Ck-1+Cl-k,where C(0)=C(1)=0 is assumed, k is the final position of pivot element, and C(l) is the total number of comparisons performed by Quicksort in sorting an array of size l, which is the number of comparisons that any partitioning algorithm can perform. Accordingly, the reason is that every element other than the pivot must be compared to the pivot. Moreover, C(k-1) in (2) is the number of comparisons of left subarray by recursive call to Quicksort, and C(l-k) is the number of comparisons of right subarray by recursive call to Quicksort. In the worst case, the parameter, k, can be assigned as 1 or l. For example, when assuming that k is equivalent to 1, then (2) becomes(3)Cl=l+Cl-1=l+l-1+Cl-2=ll+12-1,and while l≫1, the last equation becomes(4)Cl≈l22∈Ol2.Figure 1
The worst recursion tree case for Quicksort.Several appropriate pivot selection methods have been devised: (a) first element, (b) last element, (c) median-of-three elements, and (d) random element. It is worth noting that Quicksort generally chooses a pivot at random, which greatly reduces the likelihood for the worst case occurring and tends to work very well. The other means of avoiding the worst case is the median-of-three elements.


#### 2.1.2. The Best Case

As shown in Figure2, the best case has the pivot element with the middle element in the array. To know the total number C(l) for the best case, k=(l+1)/2 is considered and the results from (2) are obtained as C(l)=l+2Cl-1/2. It can be approximately examined as(5)Cl=l+2Cl2=l+22Cl4+l2=2l+22Cl22=αl+2αCl2α.Figure 2
The best recursion tree case for Quicksort.It should be noted that, after theαth calculation step, this recurrence will continue only until l=2α (otherwise we have l/2α<1), that is, until α=log2l. Thus, by putting α=log2l into the previous equation, the equation can be obtained as follows:(6)Cl=l·log2l.


#### 2.1.3. The Average Case

The average case occurs when the pivot element is near the middle element in the array (random pivot). As shown in Figure3, random pivots are used to generate the average case in the recursion tree for Quicksort.Figure 3
The average recursion tree case for Quicksort.In summary, three cases are used to understand the calculation complexity for the Quicksort algorithm. Currently, there is an axiom that could be decided.Theorem 1.
The average case in Quicksort has the expected run time ofO(l·log⁡2l), with l as the number of elements in the array.Proof.
The Harmonic numbers are given as(7)Hl=∑i=1l1i≈ln⁡l.
It is assumed that each possible pivotk is selected with equal probability, therefore, (2) can be averaged over all k, that is given as(8)Cl=1l∑k=1ll+Ck-1+Cl-k=l+1l∑k=1lCk-1+1l∑k=1lCl-k.
By substitutingi=k-1 and i=l-k into the last equation, the averaged equation can be determined as(9)∑k=1lC(k-1)=∑i=0l-1C(i),∑k=1lC(l-k)=∑i=0l-1C(i).
If the last results are taken into account, the developed recurrence becomes (see AppendixA)(10)Cl=l+2l∑i=0l-1Ci⟺lC(l)=(l+1)C(l-1)+2l-1.By dividing the last equation with l(l+1), it is written as(11)Cll+1=Cl-1l+2l-1ll+1⟺Cll+1=Cl-1l+2l.
After the assignment ofD(l)=C(l)/(l+1), the recurrence becomes as follows:(12)Dl=Dl-1+2l=Dl-2+2(l-1)+2l=⋯=D1+22+23+⋯+2(l-2)+2(l-1)+2l≈2ln⁡⁡l≈1.39log2(l),where the D(1)=0 is considered in the previous equation. In the advanced method, the recurrence is able to be performed as(13)Cl=l+1Dl≈1.39l+1log2l;moreover, when l≫1 is considered, then (14)Cl≈1.39llog2l∈Ollog2l.The worst case has the biggest or smallest pivot element in the Quicksort array, as discussed in Section2.1.1. Table 1 shows that merge sort and Quicksort have the same time complexity of O(llog2l). Quicksort is the best one of the four algorithms because its space overhead is only O(1).Table 1
Different sorting algorithms.
Sorting algorithm
Worst case time
Average case time
Space overhead
Bubble sort
O
(
l
2
)
O
(
l
2
)
O
(
1
)
Insertion sort
O
(
l
2
)
O
(
l
2
)
O
(
1
)
Merge sort
O
(
l
log
2
⁡
l
)
O
(
l
log
2
⁡
l
)
O
(
l
)
Quicksort
O
(
l
2
)
O
(
l
log
2
⁡
l
)
O
(
1
)


### 2.2. SISO Multirule System

Suppose thatr rules exist in the fuzzy expert system rule base as follows:(15)IfxisAk,thenyisBk,where Ak and Bk,k=1,2,…,r, are fuzzy sets defined in the universe of discourses V and W, respectively.


#### 2.2.1. The Comparison of CRI and IRI

(1) CRI and IRI Schemes. In order to achieve a meaningful inference result based on Zadeh’s compositional rule of inference (CRI) [2], for a given system observation there are two basic methods adopted as important illustrations. The first one is called CRI or FATI (first aggregate then infer) [3]. In this first method, for a given observation of A′, the implication is the first step performed to calculate the relational matrix given as (16)Rk=IAk,Bk,where Rk is the fuzzy implication relation for rule k and I denotes the implication method. All of the rules are then aggregated by structuring an overall fuzzy relation R which is the combination of all relational matrixes and written as(17)R=⋃k=1rRk,where R indicates an overall fuzzy relation and ∪ is defined as a combination operator of all the fuzzy implication relations. The last equation is with a final result based on a given observation A′ and shown as(18)B′=A′∘R,where ∘ represents composition within the CRI context and B′ is an inference result.The second one is called individual rule-based inference (IRI) or FITA (first infer then aggregate) [3]. For a given observation A′, we first perform the implication step to calculate the relational matrix as follows:(19)Rk=IAk,Bk,where Rk denotes the fuzzy implication relation for rule k and I is the implication method.A result for every rule based on a given observationA′ is then inferred as (20)Bk′=A′∘Rk,where Bk′ is the inference result based on rule k. Finally, all of these intermediate results are combined and determined as(21)B′=⋃k=1rBk′.Table2 showed the CRI and IRI schemes.Table 2
CRI and IRI schemes.
CRI
IRI
Step1
Implication
Implication
Step2
Aggregation
Composition
Step3
Composition
Aggregation(2) Time Complexity. In Table 3, r represents the number of rules, n is the number of elements in the input, and m indicates the number of elements in the output. Assume that minimum and maximum operations require the same effort. Applying (16) to each rule, every Rk requires nm operations and results in the implication step with r rules requires rnm operations. Based on (17), the aggregation of r relation matrixes requires r-1nm operations. The CRI composition requires nm operations for intersection and (n-1)m operations for projection. Both intersection and projection are calculated using (18). To infer a conclusion from a SISO r rules with CRI method, the total time can be easily determined as(22)tCRI=rnm+r-1nm+nm+n-1m,where tCRI denotes the CRI method time complexity. Using the result for every rule based on a given observation shown in (19), the IRI implication requires nm operations for every relational matrix Rk, and so with r relational matrixes it is just rnm operations. The IRI composition requires rnm operations for intersection and r(n-1)m operations for projection. Both intersection and projection are calculated using (20).Table 3
CRI and IRI time complexity comparison.
CRItime complexity(operations)
IRItime complexity(operations)
(1) Implication
r
n
m
r
n
m
(2) Aggregation (CRI)
r
-
1
n
m
(3) Composition
Intersection
n
m
r
n
m
Projection
n
-
1
m
r
n
-
1
m
(4) Aggregation (IRI)
r
-
1
m
Total time
r
n
m
+
r
-
1
n
m + nm+n-1m
r
n
m
+
r
n
m + rn-1m + r-1mAdopting (21), the IRI aggregation of r conclusions Bk′ will obtain r-1m operations. A conclusion from SISO r rules can be derived with the IRI method, with the total time measured as (23)tIRI=rnm+rnm+rn-1m+r-1m,where tIRI is the IRI method time complexity.The advantage of CRI compares to IRI in SISO rules expressed analytically in terms of gainG as(24)G=tIRItCRI.By substituting (22) and (23) into the last equation, the gain becomes (25)G=tIRItCRI=2rnm+rn-1m+r-1mrnm+r-1nm+nm+n-1m=3rn-12rn+n-1≈32>1.The formula shows that gainG is always bigger than 1. We pointed out that the CRI method time complexity is less than the IRI method time complexity in the SISO rules expert system.(3) Space Complexity. In Table 4, the same definition expressed in Table 3 is used for r, n, and m, assuming that every element requires one cell. Applying (16) to each rule, each Rk requires nm cells and results in the implication step with r rules requires rnm cells. Based on (17), it is clear that the aggregation of r relation matrix requires nm cells. Using (18), it is known that the composition of CRI requires nm cells for intersection and m cells for projection, respectively. In general, to infer a conclusion from SISO r rules with the CRI method, the required space is determined using the biggest space from all steps and obtained as (26)Ornm.Table 4
CRI and IRI space complexity comparison.
CRI space complexity (cells)
IRI space complexity (cells)
(1) Implication
r
n
m
r
n
m
(2) Aggregation (CRI)
n
m
(3) Composition
Intersection
n
m
r
n
m
Projection
m
r
m
(4) Aggregation (IRI)
m
The biggest space of all steps
r
n
m
r
n
mTo determine the implication that IRI requiresnm cells for every relational matrix Rk using (19), that is, with r, relational matrixes rnm cells are necessary. Based on (20), the IRI composition requires rnm cells for intersection and rm cells for projection, respectively. Therefore, with (21) the aggregation of r conclusions Bk′ requires m cells. Hence, to infer a conclusion from SISO r rules with the IRI method, the required space can be determined using the biggest space from all steps and written as(27)Ornm.For the purpose of optimization, CRI combines step (1) (implication) with step (2) (aggregation); thus, it is easily understood that CRI needs a space ofO(nm). IRI requires a space of O(rnm) to store r relational matrixes in the implication step. It is worth noting that the CRI method space complexity is less than the IRI method space complexity in the SISO rules expert system.


#### 2.2.2. CRI and SCRI

(1) CRI. As mentioned in Section 2.2.1(1) the first CRI method step is the implication step, which includes two substeps. The first substep is cylindrical extension defined as(28)Ak_ex=a11ka12k⋯a1mka21ka22k⋯a2mk⋮⋮⋯⋮an1kan2k⋯anmkn×m,where Ak_ex is extended by Ak, aijk=aik, with Ak=[aik]i=1n,i=1,2,…,n,j=1,2,…,m,k=1,2,…,r: (29)Bk_ex=b11kb12k⋯b1mkb21kb22k⋯b2mk⋮⋮⋯⋮bn1kbn2k⋯bnmkn×m,where Bk_ex is extended by Bk, bijk=bjk, with Bk=[bjk]j=1m, i=1,2,…,n, j=1,2,…,m, k=1,2,…,r.Filling all of the columns in the related matrix using theX-projection is cylindrical extension from X-projection which is shown in (28). Similarly, cylindrical extension from Y-projection means filling all of the rows in the relation matrix using the Y-projection as shown in (29). Calculating relation matrix is the second substep to be defined and it is written as(30)Rk=min⁡Ak_ex,Bk_ex=q11kq12k⋯q1mkq21kq22k⋯q2mk⋮⋮⋯⋮qn1kqn2k⋯qnmkn×m,where Rk is the relation matrix for rule k and qijk=min⁡(aijk,bijk), i=1,2,….,n; j=1,2,…,m. The implication is “min” as Mamdani fuzzy model. Aggregation, the second CRI method step, is defined as(31)R=⋃k=1rRk,where R is the overall relation matrix, which is calculated by combining all of the relation matrix Rk with k=1,2,…,r. Composition is the final CRI step and it is defined as (see Appendix B)(32)B′=A′∘R=sup⁡min⁡A′_ex,R=sup⁡b11′b12′⋯b1m′b21′b22′⋯b2m′⋮⋮⋯⋮bn1′bn2′⋯bnm′n×m=b1′b2′⋯bm′,where A′_ex is extended by A′,B′ is the inference result which is calculated by compositing the observation A′ with the overall relational matrix R, and ∘ represents the composition method.(2) SCRI (Sort CRI). In this subsection, the SCRI method is introduced. It includes three steps. The first step is implication which has two substeps. The first substep is sorting program and the second substep is getting relational matrix. The second step is aggregation defined as R=⋃k=1rRk. Composition is the third step and given as B′(v)=A′∘R=sup⁡min⁡A′_ex,R, where A′_ex is extended by A′. Moreover, let us discuss the SCRI method implication step in detail. The SCRI implication has two substeps. The matrix Ck is necessary for processing the first sorting program step, which can be expressed as(33)Ck=a1ka2k⋯ankb1kb2k⋯bmk1.11.2⋯1.n2.12.2⋯2.m2×(n+m),where the elements in the first row of (33) are a combination of Ak and Bk with Ak=[a1k,a2k,…,ank],Bk=[b1k,b2k,…,bmk]. In addition, the second row of (33) has two arguments for every cell in the first row. The first argument could be “1” or “2” depending on whether the cell in the first row belongs to Ak or Bk, respectively. Moreover, the second argument for the second row in (33) could be ank or bmk; that is, a1k=b1k=1,a2k=b2k=2,…, and ank=n, bmk=m, where ank and bmk belong to Ak and Bk, respectively.To sort the matrixCk based on the 1st row is the second step which is obtained as (34)Ck=quicksortCk,1strow.The Quicksort algorithm then sorts theCk as(35)Ck=c1kc2k⋯cn+mk⋯⋯⋯xn+myn+m2×(n+m),where c1k is minimum of the 1st row, cn+mk is maximum of the 1st row, and xn+m is 1 or 2 to indicate that the value cn+mk belongs to Ak or Bk, respectively. yn+m in (35) is used to specify the position of the value cn+mk in Ak or Bk depending on whether xn+m is 1 or 2, respectively. The second substep is getting relational matrix, which has n+m steps. In the first step, consider the condition of xn+m asifxn+m=1, then all values in the yn+mth row of Rk are equal to cn+mk;ifxn+m=2, then all values in the yn+mth column of Rk are equal to cn+mk.In the second step, consider the condition of xn+m-1, and keep on continuing until x1.(3) CRI and SCRI Schemes. Table 5 showed the CRI and SCRI schemes. In the implication step, the main CRI operation is “calculating relational matrix” and the main SCRI operation is “sorting program.”Table 5
CRI and SCRI schemes.
CRI
SCRI
Implication
Implication
Cylindrical extension
Sorting program
Calculating relational matrix
Getting relational matrix
Aggregation
Aggregation
Composition
Composition(4) Time Complexity. SCRI is an improvement method from correcting the CRI implication step. The time complexity of the implication step for these two methods is compared and the results are shown in Table 6. The same r, n, and m parameters and the Quicksort are adopted for the SCRI sorting program. Following Theorem 1, the time complexity of an array with n+m elements is On+mlog2n+m. With SISO r-rule fuzzy system, the time complexity of the implication step of SCRI method is denoted as(36)Orn+mlog2n+m.Based on (30), the time complexity of the implication step for CRI method can be determined as(37)Ornm.Table 6
CRI and SCRI time complexity comparison results.
CRI time complexity (min operations)
SCRI time complexity (min operations)
Implication
O
(
r
n
m
)
O
r
n
+
m
log
2
⁡
n
+
mThe input dimension equals the output dimension in Figure4 and the number of rules is 10. The red line (curve for CRI) shows the relation of x (dimension of input and output) and y (operations), and the blue line (dash curve for SCRI) shows the relation of x (dimension of input and output) and y (operations), respectively. Moreover, the green line shows a reference line with the input dimension as 40 and the output dimension as 40. The red point in the red line with input dimension = 40, output dimension = 40, and the number of rules = 10 shows CRI=16000 operations. The blue point at the blue line with input dimension = 40, output dimension = 40, and number of rules = 10 shows SCRI=5058 operations. It is clear to see that the CRI method time complexity is greater than the SCRI method time complexity.Figure 4
CRI and SCRI implication step time complexity comparison withr=10, n=m.(5) Space Complexity. In this subsection SCRI is discussed as an improvement in the CRI implication step. The implication step space complexity of the CRI and SCRI methods is shown in Table 7. By substituting r, n, and m of the output elements into (30) for every relational matrix, the CRI needs a space of O(nm). With SISO r rules the CRI needs a space of O(rnm). Thus, based on (34), for every relational matrix, it is known that SCRI needs a space of O(n+m). With SISO r rules, SCRI needs a space of O(rnm) to store r relational matrixes.Table 7
CRI and SCRI space complexity comparison.
CRI
space complexity
(cells)
SCRI
space complexity
(cells)
Implication
1 relation matrix
O
(
n
m
)
1 relation matrix
O
(
n
+
m
)
r relation matrixes
O
(
r
n
m
)
r relation matrixes
O
(
r
n
m
)Based on (34), for every relational matrix, SCRI just needs a space of O(n+m) but applying (30) CRI needs a space of O(nm).


#### 2.2.3. IRI and SIRI

(1) IRI. The first step in the IRI method is the implication step as defined in Section 2.2.1(1), which includes two substeps. The first substep is cylindrical extension defined as(38)Ak_ex=a11ka12k⋯a1mka21ka22k⋯a2mk⋮⋮⋯⋮an1kan2k⋯anmkn×m,where Ak_ex is extended by Ak, aijk=aik, with Ak=[aik]i=1n, i=1,2,…,n, j=1,2,…,m, k=1,2,…,r:(39)Bk_ex=b11kb12k⋯b1mkb21kb22k⋯b2mk⋮⋮⋯⋮bn1kbn2k⋯bnmkn×m,where Bk_ex is extended by Bk, bijk=bjk, with Bk=[bjk]j=1m, i=1,2,…,n, j=1,2,…,m, k=1,2,…,r.The second substep is calculating relation matrix defined as(40)Rk=min⁡Ak_ex,Bk_ex,where Rk is the relation matrix of rule k. The implication is “min” as Mamdani fuzzy model. The second step of IRI method is composition which is defined as(41)Bk′=A′∘Rk,where Bk′ is the inference result of rule k and it is calculated by composing observation A′ with the relational matrix Rk of rule k and ∘ represents the composition method. The third step of IRI is aggregation defined as(42)B′=⋃k=1rBk′,where B′ is the final inference result. It is calculated by combining all of the inference results Bk′ with k=1,2,…,r.(2) SIRI (Sort IRI). Containing three steps for SIRI method, the first step is implication which involves two substeps. The first substep is sorting program and the second substep is getting relational matrix. The second step is composition defined as Bk′=A′∘Rk, and the third one is aggregation defined as B′=⋃k=1rBk′.Furthermore, the SIRI implication has two more substeps. The first substep is sorting program. The matrixCk is generated as (43)Ck=a1ka2k⋯ankb1kb2k⋯bmk1.11.2⋯1.n2.12.2⋯2.m2×(n+m),where the elements in the first row of (43) are the combination of Ak and Bk with Ak=[a1k,a2k,…,ank],Bk=[b1k,b2k,…,bmk]. In addition, the second row of (43) has two arguments for every cell in the first row, and the first argument could be “1” or “2” depending on the cell of the first row belonging to Ak or Bk, respectively. Moreover, the second argument of the second row in (43) could be ank or bmk; that is, a1k=b1k=1, a2k=b2k=2,…, and ank=n, bmk=m, where ank and bmk belong to Ak and Bk, respectively.Sort the matrixCk based on the 1st row and obtained as(44)Ck=quicksortCk,1strow.After taking the Quicksort algorithm, the final Ck is sorted as (45)Ck=c1kc2k⋯cn+mk⋯⋯⋯xn+myn+m2×(n+m),where c1k is minimum of the 1st row and cn+mk is maximum of the 1st row and xn+m is 1 or 2 to indicate the value cn+mk belonging to Ak or Bk, respectively. yn+m in (45) is used to define the position of the value cn+mk in Ak or Bk depending on xn+m which is 1 or 2, respectively. The second substep is getting relational matrix, which has n+m steps. In the first step, let us consider the condition of xn+m as ifxn+m=1, then all values in the yn+mth row of Rk are equal to cn+mk;ifxn+m=2, then all values in the yn+mth column of Rk are equal to cn+mk.In the next step, consider the condition ofxn+m-1, and keep on the algorithm until x1.(3) IRI and SIRI Schemes. The main IRI operation is “calculating relational matrix” and the main operation of the SIRI belongs to “sorting program.” The operation schemes of IRI and SIRI are listed in Table 8.Table 8
IRI and SIRI schemes.
IRI
SIRI
Implication
Implication
Cylindrical extension
Sorting program
Calculating relational matrix
Getting relational matrix
Composition
Composition
Aggregation
Aggregation(4) Time Complexity. The comparison results are shown in Table 9. Three parameters r, n, and m and Quicksort are used for the SIRI sorting program to verify the time complexity. The time complexity of an array with n+m elements is On+mlog⁡2n+m which can be determined from Theorem 1 again. With SISO r-rule fuzzy systems, the time complexity of the implication step of SIRI method is(46)Orn+mlog⁡2n+m.Table 9
Comparison of the time complexity of IRI and SIRI.
IRI time complexity (min operations)
SIRI time complexity (min operations)
Implication
O
(
r
n
m
)
O
r
n
+
m
log
2
⁡
(
n
+
m
)Furthermore, the time complexity of the implication step of IRI method can be obtained from (40) and expressed as(47)Ornm.In order to understand the operation complexity of these methods, the results from time complexity comparison are shown in Figure5. The input dimension is considered equal to the output dimension. The number of rules is set to 10. Red line (curve for IRI) shows the relation of x (dimension of input and output) and y (operations). On the contrary, the blue line (dash curve for SIRI) represents the relation of x (dimension of input and output) and y (operations). On the other hand, the green line is a reference line which with the input dimension is 50 and the output dimension is 50. Red point, at the red line with input dimension = 50, output dimension = 50, number of rules = 10, shows operations of IRI=25000 operations. Blue point, at the blue line with input dimension = 50, output dimension = 50, and number of rules = 10, showed operations of SIRI=6644 operations. As previously described, it is clear that the IRI operations are definitely larger than the SIRI operations.Figure 5
IRI and SIRI implication step time complexity comparison results withr=10, n=m.(5) Space Complexity. In this subsection, the space complexity of the SIRI implication step is shown. This is an improvement in the IRI implication step. In Table 10, the space complexity of IRI and SIRI is illustrated with the r, n, and m parameters again. By taking account of every relational matrix into (40), the space complexity of O(nm) is for IRI; on the contrary, with SISO r rules the IRI requires space of O(rnm).Table 10
IRI and SIRI space complexity comparison.
IRI
space complexity
(cells)
SIRI
space complexity
(cells)
Implication
1 relation matrix
O
(
n
m
)
1 relation matrix
O
(
n
+
m
)
r relation matrixes
O
(
r
n
m
)
r relation matrixes
O
(
r
n
m
)Based on (44) for every relational matrix, SIRI just needs a space of O(n+m) but applying (40) IRI needs a space of O(nm).


## 2.1. Quicksort

This study adopted a method referred to as Quicksort, a divide-and-conquer method, which proceeds through four steps: (1) arbitrarily select an element in the array (the pivot), (2) divide the array into two subarrays of uneven size (the partition phase), (3) sort the subarrays recursively, and (4) position the pivot between the two sorted subarrays to obtain the final sorted array. The Quicksort performance depends on the pivot elements in the array, as outlined below.


### 2.1.1. The Worst Case

The worst case scenario occurs when the pivot element is the largest or smallest element in the array. In Figure1, the pivot element is the smallest element in the array. The total number C(l) of comparisons performed by Quicksort in sorting an array of size l is calculated as (2)Cl=l+Ck-1+Cl-k,where C(0)=C(1)=0 is assumed, k is the final position of pivot element, and C(l) is the total number of comparisons performed by Quicksort in sorting an array of size l, which is the number of comparisons that any partitioning algorithm can perform. Accordingly, the reason is that every element other than the pivot must be compared to the pivot. Moreover, C(k-1) in (2) is the number of comparisons of left subarray by recursive call to Quicksort, and C(l-k) is the number of comparisons of right subarray by recursive call to Quicksort. In the worst case, the parameter, k, can be assigned as 1 or l. For example, when assuming that k is equivalent to 1, then (2) becomes(3)Cl=l+Cl-1=l+l-1+Cl-2=ll+12-1,and while l≫1, the last equation becomes(4)Cl≈l22∈Ol2.Figure 1
The worst recursion tree case for Quicksort.Several appropriate pivot selection methods have been devised: (a) first element, (b) last element, (c) median-of-three elements, and (d) random element. It is worth noting that Quicksort generally chooses a pivot at random, which greatly reduces the likelihood for the worst case occurring and tends to work very well. The other means of avoiding the worst case is the median-of-three elements.


### 2.1.2. The Best Case

As shown in Figure2, the best case has the pivot element with the middle element in the array. To know the total number C(l) for the best case, k=(l+1)/2 is considered and the results from (2) are obtained as C(l)=l+2Cl-1/2. It can be approximately examined as(5)Cl=l+2Cl2=l+22Cl4+l2=2l+22Cl22=αl+2αCl2α.Figure 2
The best recursion tree case for Quicksort.It should be noted that, after theαth calculation step, this recurrence will continue only until l=2α (otherwise we have l/2α<1), that is, until α=log2l. Thus, by putting α=log2l into the previous equation, the equation can be obtained as follows:(6)Cl=l·log2l.


### 2.1.3. The Average Case

The average case occurs when the pivot element is near the middle element in the array (random pivot). As shown in Figure3, random pivots are used to generate the average case in the recursion tree for Quicksort.Figure 3
The average recursion tree case for Quicksort.In summary, three cases are used to understand the calculation complexity for the Quicksort algorithm. Currently, there is an axiom that could be decided.Theorem 1.
The average case in Quicksort has the expected run time ofO(l·log⁡2l), with l as the number of elements in the array.Proof.
The Harmonic numbers are given as(7)Hl=∑i=1l1i≈ln⁡l.
It is assumed that each possible pivotk is selected with equal probability, therefore, (2) can be averaged over all k, that is given as(8)Cl=1l∑k=1ll+Ck-1+Cl-k=l+1l∑k=1lCk-1+1l∑k=1lCl-k.
By substitutingi=k-1 and i=l-k into the last equation, the averaged equation can be determined as(9)∑k=1lC(k-1)=∑i=0l-1C(i),∑k=1lC(l-k)=∑i=0l-1C(i).
If the last results are taken into account, the developed recurrence becomes (see AppendixA)(10)Cl=l+2l∑i=0l-1Ci⟺lC(l)=(l+1)C(l-1)+2l-1.By dividing the last equation with l(l+1), it is written as(11)Cll+1=Cl-1l+2l-1ll+1⟺Cll+1=Cl-1l+2l.
After the assignment ofD(l)=C(l)/(l+1), the recurrence becomes as follows:(12)Dl=Dl-1+2l=Dl-2+2(l-1)+2l=⋯=D1+22+23+⋯+2(l-2)+2(l-1)+2l≈2ln⁡⁡l≈1.39log2(l),where the D(1)=0 is considered in the previous equation. In the advanced method, the recurrence is able to be performed as(13)Cl=l+1Dl≈1.39l+1log2l;moreover, when l≫1 is considered, then (14)Cl≈1.39llog2l∈Ollog2l.The worst case has the biggest or smallest pivot element in the Quicksort array, as discussed in Section2.1.1. Table 1 shows that merge sort and Quicksort have the same time complexity of O(llog2l). Quicksort is the best one of the four algorithms because its space overhead is only O(1).Table 1
Different sorting algorithms.
Sorting algorithm
Worst case time
Average case time
Space overhead
Bubble sort
O
(
l
2
)
O
(
l
2
)
O
(
1
)
Insertion sort
O
(
l
2
)
O
(
l
2
)
O
(
1
)
Merge sort
O
(
l
log
2
⁡
l
)
O
(
l
log
2
⁡
l
)
O
(
l
)
Quicksort
O
(
l
2
)
O
(
l
log
2
⁡
l
)
O
(
1
)


## 2.1.1. The Worst Case

The worst case scenario occurs when the pivot element is the largest or smallest element in the array. In Figure1, the pivot element is the smallest element in the array. The total number C(l) of comparisons performed by Quicksort in sorting an array of size l is calculated as (2)Cl=l+Ck-1+Cl-k,where C(0)=C(1)=0 is assumed, k is the final position of pivot element, and C(l) is the total number of comparisons performed by Quicksort in sorting an array of size l, which is the number of comparisons that any partitioning algorithm can perform. Accordingly, the reason is that every element other than the pivot must be compared to the pivot. Moreover, C(k-1) in (2) is the number of comparisons of left subarray by recursive call to Quicksort, and C(l-k) is the number of comparisons of right subarray by recursive call to Quicksort. In the worst case, the parameter, k, can be assigned as 1 or l. For example, when assuming that k is equivalent to 1, then (2) becomes(3)Cl=l+Cl-1=l+l-1+Cl-2=ll+12-1,and while l≫1, the last equation becomes(4)Cl≈l22∈Ol2.Figure 1
The worst recursion tree case for Quicksort.Several appropriate pivot selection methods have been devised: (a) first element, (b) last element, (c) median-of-three elements, and (d) random element. It is worth noting that Quicksort generally chooses a pivot at random, which greatly reduces the likelihood for the worst case occurring and tends to work very well. The other means of avoiding the worst case is the median-of-three elements.


## 2.1.2. The Best Case

As shown in Figure2, the best case has the pivot element with the middle element in the array. To know the total number C(l) for the best case, k=(l+1)/2 is considered and the results from (2) are obtained as C(l)=l+2Cl-1/2. It can be approximately examined as(5)Cl=l+2Cl2=l+22Cl4+l2=2l+22Cl22=αl+2αCl2α.Figure 2
The best recursion tree case for Quicksort.It should be noted that, after theαth calculation step, this recurrence will continue only until l=2α (otherwise we have l/2α<1), that is, until α=log2l. Thus, by putting α=log2l into the previous equation, the equation can be obtained as follows:(6)Cl=l·log2l.


## 2.1.3. The Average Case

The average case occurs when the pivot element is near the middle element in the array (random pivot). As shown in Figure3, random pivots are used to generate the average case in the recursion tree for Quicksort.Figure 3
The average recursion tree case for Quicksort.In summary, three cases are used to understand the calculation complexity for the Quicksort algorithm. Currently, there is an axiom that could be decided.Theorem 1.
The average case in Quicksort has the expected run time ofO(l·log⁡2l), with l as the number of elements in the array.Proof.
The Harmonic numbers are given as(7)Hl=∑i=1l1i≈ln⁡l.
It is assumed that each possible pivotk is selected with equal probability, therefore, (2) can be averaged over all k, that is given as(8)Cl=1l∑k=1ll+Ck-1+Cl-k=l+1l∑k=1lCk-1+1l∑k=1lCl-k.
By substitutingi=k-1 and i=l-k into the last equation, the averaged equation can be determined as(9)∑k=1lC(k-1)=∑i=0l-1C(i),∑k=1lC(l-k)=∑i=0l-1C(i).
If the last results are taken into account, the developed recurrence becomes (see AppendixA)(10)Cl=l+2l∑i=0l-1Ci⟺lC(l)=(l+1)C(l-1)+2l-1.By dividing the last equation with l(l+1), it is written as(11)Cll+1=Cl-1l+2l-1ll+1⟺Cll+1=Cl-1l+2l.
After the assignment ofD(l)=C(l)/(l+1), the recurrence becomes as follows:(12)Dl=Dl-1+2l=Dl-2+2(l-1)+2l=⋯=D1+22+23+⋯+2(l-2)+2(l-1)+2l≈2ln⁡⁡l≈1.39log2(l),where the D(1)=0 is considered in the previous equation. In the advanced method, the recurrence is able to be performed as(13)Cl=l+1Dl≈1.39l+1log2l;moreover, when l≫1 is considered, then (14)Cl≈1.39llog2l∈Ollog2l.The worst case has the biggest or smallest pivot element in the Quicksort array, as discussed in Section2.1.1. Table 1 shows that merge sort and Quicksort have the same time complexity of O(llog2l). Quicksort is the best one of the four algorithms because its space overhead is only O(1).Table 1
Different sorting algorithms.
Sorting algorithm
Worst case time
Average case time
Space overhead
Bubble sort
O
(
l
2
)
O
(
l
2
)
O
(
1
)
Insertion sort
O
(
l
2
)
O
(
l
2
)
O
(
1
)
Merge sort
O
(
l
log
2
⁡
l
)
O
(
l
log
2
⁡
l
)
O
(
l
)
Quicksort
O
(
l
2
)
O
(
l
log
2
⁡
l
)
O
(
1
)


## 2.2. SISO Multirule System

Suppose thatr rules exist in the fuzzy expert system rule base as follows:(15)IfxisAk,thenyisBk,where Ak and Bk,k=1,2,…,r, are fuzzy sets defined in the universe of discourses V and W, respectively.


### 2.2.1. The Comparison of CRI and IRI

(1) CRI and IRI Schemes. In order to achieve a meaningful inference result based on Zadeh’s compositional rule of inference (CRI) [2], for a given system observation there are two basic methods adopted as important illustrations. The first one is called CRI or FATI (first aggregate then infer) [3]. In this first method, for a given observation of A′, the implication is the first step performed to calculate the relational matrix given as (16)Rk=IAk,Bk,where Rk is the fuzzy implication relation for rule k and I denotes the implication method. All of the rules are then aggregated by structuring an overall fuzzy relation R which is the combination of all relational matrixes and written as(17)R=⋃k=1rRk,where R indicates an overall fuzzy relation and ∪ is defined as a combination operator of all the fuzzy implication relations. The last equation is with a final result based on a given observation A′ and shown as(18)B′=A′∘R,where ∘ represents composition within the CRI context and B′ is an inference result.The second one is called individual rule-based inference (IRI) or FITA (first infer then aggregate) [3]. For a given observation A′, we first perform the implication step to calculate the relational matrix as follows:(19)Rk=IAk,Bk,where Rk denotes the fuzzy implication relation for rule k and I is the implication method.A result for every rule based on a given observationA′ is then inferred as (20)Bk′=A′∘Rk,where Bk′ is the inference result based on rule k. Finally, all of these intermediate results are combined and determined as(21)B′=⋃k=1rBk′.Table2 showed the CRI and IRI schemes.Table 2
CRI and IRI schemes.
CRI
IRI
Step1
Implication
Implication
Step2
Aggregation
Composition
Step3
Composition
Aggregation(2) Time Complexity. In Table 3, r represents the number of rules, n is the number of elements in the input, and m indicates the number of elements in the output. Assume that minimum and maximum operations require the same effort. Applying (16) to each rule, every Rk requires nm operations and results in the implication step with r rules requires rnm operations. Based on (17), the aggregation of r relation matrixes requires r-1nm operations. The CRI composition requires nm operations for intersection and (n-1)m operations for projection. Both intersection and projection are calculated using (18). To infer a conclusion from a SISO r rules with CRI method, the total time can be easily determined as(22)tCRI=rnm+r-1nm+nm+n-1m,where tCRI denotes the CRI method time complexity. Using the result for every rule based on a given observation shown in (19), the IRI implication requires nm operations for every relational matrix Rk, and so with r relational matrixes it is just rnm operations. The IRI composition requires rnm operations for intersection and r(n-1)m operations for projection. Both intersection and projection are calculated using (20).Table 3
CRI and IRI time complexity comparison.
CRItime complexity(operations)
IRItime complexity(operations)
(1) Implication
r
n
m
r
n
m
(2) Aggregation (CRI)
r
-
1
n
m
(3) Composition
Intersection
n
m
r
n
m
Projection
n
-
1
m
r
n
-
1
m
(4) Aggregation (IRI)
r
-
1
m
Total time
r
n
m
+
r
-
1
n
m + nm+n-1m
r
n
m
+
r
n
m + rn-1m + r-1mAdopting (21), the IRI aggregation of r conclusions Bk′ will obtain r-1m operations. A conclusion from SISO r rules can be derived with the IRI method, with the total time measured as (23)tIRI=rnm+rnm+rn-1m+r-1m,where tIRI is the IRI method time complexity.The advantage of CRI compares to IRI in SISO rules expressed analytically in terms of gainG as(24)G=tIRItCRI.By substituting (22) and (23) into the last equation, the gain becomes (25)G=tIRItCRI=2rnm+rn-1m+r-1mrnm+r-1nm+nm+n-1m=3rn-12rn+n-1≈32>1.The formula shows that gainG is always bigger than 1. We pointed out that the CRI method time complexity is less than the IRI method time complexity in the SISO rules expert system.(3) Space Complexity. In Table 4, the same definition expressed in Table 3 is used for r, n, and m, assuming that every element requires one cell. Applying (16) to each rule, each Rk requires nm cells and results in the implication step with r rules requires rnm cells. Based on (17), it is clear that the aggregation of r relation matrix requires nm cells. Using (18), it is known that the composition of CRI requires nm cells for intersection and m cells for projection, respectively. In general, to infer a conclusion from SISO r rules with the CRI method, the required space is determined using the biggest space from all steps and obtained as (26)Ornm.Table 4
CRI and IRI space complexity comparison.
CRI space complexity (cells)
IRI space complexity (cells)
(1) Implication
r
n
m
r
n
m
(2) Aggregation (CRI)
n
m
(3) Composition
Intersection
n
m
r
n
m
Projection
m
r
m
(4) Aggregation (IRI)
m
The biggest space of all steps
r
n
m
r
n
mTo determine the implication that IRI requiresnm cells for every relational matrix Rk using (19), that is, with r, relational matrixes rnm cells are necessary. Based on (20), the IRI composition requires rnm cells for intersection and rm cells for projection, respectively. Therefore, with (21) the aggregation of r conclusions Bk′ requires m cells. Hence, to infer a conclusion from SISO r rules with the IRI method, the required space can be determined using the biggest space from all steps and written as(27)Ornm.For the purpose of optimization, CRI combines step (1) (implication) with step (2) (aggregation); thus, it is easily understood that CRI needs a space ofO(nm). IRI requires a space of O(rnm) to store r relational matrixes in the implication step. It is worth noting that the CRI method space complexity is less than the IRI method space complexity in the SISO rules expert system.


### 2.2.2. CRI and SCRI

(1) CRI. As mentioned in Section 2.2.1(1) the first CRI method step is the implication step, which includes two substeps. The first substep is cylindrical extension defined as(28)Ak_ex=a11ka12k⋯a1mka21ka22k⋯a2mk⋮⋮⋯⋮an1kan2k⋯anmkn×m,where Ak_ex is extended by Ak, aijk=aik, with Ak=[aik]i=1n,i=1,2,…,n,j=1,2,…,m,k=1,2,…,r: (29)Bk_ex=b11kb12k⋯b1mkb21kb22k⋯b2mk⋮⋮⋯⋮bn1kbn2k⋯bnmkn×m,where Bk_ex is extended by Bk, bijk=bjk, with Bk=[bjk]j=1m, i=1,2,…,n, j=1,2,…,m, k=1,2,…,r.Filling all of the columns in the related matrix using theX-projection is cylindrical extension from X-projection which is shown in (28). Similarly, cylindrical extension from Y-projection means filling all of the rows in the relation matrix using the Y-projection as shown in (29). Calculating relation matrix is the second substep to be defined and it is written as(30)Rk=min⁡Ak_ex,Bk_ex=q11kq12k⋯q1mkq21kq22k⋯q2mk⋮⋮⋯⋮qn1kqn2k⋯qnmkn×m,where Rk is the relation matrix for rule k and qijk=min⁡(aijk,bijk), i=1,2,….,n; j=1,2,…,m. The implication is “min” as Mamdani fuzzy model. Aggregation, the second CRI method step, is defined as(31)R=⋃k=1rRk,where R is the overall relation matrix, which is calculated by combining all of the relation matrix Rk with k=1,2,…,r. Composition is the final CRI step and it is defined as (see Appendix B)(32)B′=A′∘R=sup⁡min⁡A′_ex,R=sup⁡b11′b12′⋯b1m′b21′b22′⋯b2m′⋮⋮⋯⋮bn1′bn2′⋯bnm′n×m=b1′b2′⋯bm′,where A′_ex is extended by A′,B′ is the inference result which is calculated by compositing the observation A′ with the overall relational matrix R, and ∘ represents the composition method.(2) SCRI (Sort CRI). In this subsection, the SCRI method is introduced. It includes three steps. The first step is implication which has two substeps. The first substep is sorting program and the second substep is getting relational matrix. The second step is aggregation defined as R=⋃k=1rRk. Composition is the third step and given as B′(v)=A′∘R=sup⁡min⁡A′_ex,R, where A′_ex is extended by A′. Moreover, let us discuss the SCRI method implication step in detail. The SCRI implication has two substeps. The matrix Ck is necessary for processing the first sorting program step, which can be expressed as(33)Ck=a1ka2k⋯ankb1kb2k⋯bmk1.11.2⋯1.n2.12.2⋯2.m2×(n+m),where the elements in the first row of (33) are a combination of Ak and Bk with Ak=[a1k,a2k,…,ank],Bk=[b1k,b2k,…,bmk]. In addition, the second row of (33) has two arguments for every cell in the first row. The first argument could be “1” or “2” depending on whether the cell in the first row belongs to Ak or Bk, respectively. Moreover, the second argument for the second row in (33) could be ank or bmk; that is, a1k=b1k=1,a2k=b2k=2,…, and ank=n, bmk=m, where ank and bmk belong to Ak and Bk, respectively.To sort the matrixCk based on the 1st row is the second step which is obtained as (34)Ck=quicksortCk,1strow.The Quicksort algorithm then sorts theCk as(35)Ck=c1kc2k⋯cn+mk⋯⋯⋯xn+myn+m2×(n+m),where c1k is minimum of the 1st row, cn+mk is maximum of the 1st row, and xn+m is 1 or 2 to indicate that the value cn+mk belongs to Ak or Bk, respectively. yn+m in (35) is used to specify the position of the value cn+mk in Ak or Bk depending on whether xn+m is 1 or 2, respectively. The second substep is getting relational matrix, which has n+m steps. In the first step, consider the condition of xn+m asifxn+m=1, then all values in the yn+mth row of Rk are equal to cn+mk;ifxn+m=2, then all values in the yn+mth column of Rk are equal to cn+mk.In the second step, consider the condition of xn+m-1, and keep on continuing until x1.(3) CRI and SCRI Schemes. Table 5 showed the CRI and SCRI schemes. In the implication step, the main CRI operation is “calculating relational matrix” and the main SCRI operation is “sorting program.”Table 5
CRI and SCRI schemes.
CRI
SCRI
Implication
Implication
Cylindrical extension
Sorting program
Calculating relational matrix
Getting relational matrix
Aggregation
Aggregation
Composition
Composition(4) Time Complexity. SCRI is an improvement method from correcting the CRI implication step. The time complexity of the implication step for these two methods is compared and the results are shown in Table 6. The same r, n, and m parameters and the Quicksort are adopted for the SCRI sorting program. Following Theorem 1, the time complexity of an array with n+m elements is On+mlog2n+m. With SISO r-rule fuzzy system, the time complexity of the implication step of SCRI method is denoted as(36)Orn+mlog2n+m.Based on (30), the time complexity of the implication step for CRI method can be determined as(37)Ornm.Table 6
CRI and SCRI time complexity comparison results.
CRI time complexity (min operations)
SCRI time complexity (min operations)
Implication
O
(
r
n
m
)
O
r
n
+
m
log
2
⁡
n
+
mThe input dimension equals the output dimension in Figure4 and the number of rules is 10. The red line (curve for CRI) shows the relation of x (dimension of input and output) and y (operations), and the blue line (dash curve for SCRI) shows the relation of x (dimension of input and output) and y (operations), respectively. Moreover, the green line shows a reference line with the input dimension as 40 and the output dimension as 40. The red point in the red line with input dimension = 40, output dimension = 40, and the number of rules = 10 shows CRI=16000 operations. The blue point at the blue line with input dimension = 40, output dimension = 40, and number of rules = 10 shows SCRI=5058 operations. It is clear to see that the CRI method time complexity is greater than the SCRI method time complexity.Figure 4
CRI and SCRI implication step time complexity comparison withr=10, n=m.(5) Space Complexity. In this subsection SCRI is discussed as an improvement in the CRI implication step. The implication step space complexity of the CRI and SCRI methods is shown in Table 7. By substituting r, n, and m of the output elements into (30) for every relational matrix, the CRI needs a space of O(nm). With SISO r rules the CRI needs a space of O(rnm). Thus, based on (34), for every relational matrix, it is known that SCRI needs a space of O(n+m). With SISO r rules, SCRI needs a space of O(rnm) to store r relational matrixes.Table 7
CRI and SCRI space complexity comparison.
CRI
space complexity
(cells)
SCRI
space complexity
(cells)
Implication
1 relation matrix
O
(
n
m
)
1 relation matrix
O
(
n
+
m
)
r relation matrixes
O
(
r
n
m
)
r relation matrixes
O
(
r
n
m
)Based on (34), for every relational matrix, SCRI just needs a space of O(n+m) but applying (30) CRI needs a space of O(nm).


### 2.2.3. IRI and SIRI

(1) IRI. The first step in the IRI method is the implication step as defined in Section 2.2.1(1), which includes two substeps. The first substep is cylindrical extension defined as(38)Ak_ex=a11ka12k⋯a1mka21ka22k⋯a2mk⋮⋮⋯⋮an1kan2k⋯anmkn×m,where Ak_ex is extended by Ak, aijk=aik, with Ak=[aik]i=1n, i=1,2,…,n, j=1,2,…,m, k=1,2,…,r:(39)Bk_ex=b11kb12k⋯b1mkb21kb22k⋯b2mk⋮⋮⋯⋮bn1kbn2k⋯bnmkn×m,where Bk_ex is extended by Bk, bijk=bjk, with Bk=[bjk]j=1m, i=1,2,…,n, j=1,2,…,m, k=1,2,…,r.The second substep is calculating relation matrix defined as(40)Rk=min⁡Ak_ex,Bk_ex,where Rk is the relation matrix of rule k. The implication is “min” as Mamdani fuzzy model. The second step of IRI method is composition which is defined as(41)Bk′=A′∘Rk,where Bk′ is the inference result of rule k and it is calculated by composing observation A′ with the relational matrix Rk of rule k and ∘ represents the composition method. The third step of IRI is aggregation defined as(42)B′=⋃k=1rBk′,where B′ is the final inference result. It is calculated by combining all of the inference results Bk′ with k=1,2,…,r.(2) SIRI (Sort IRI). Containing three steps for SIRI method, the first step is implication which involves two substeps. The first substep is sorting program and the second substep is getting relational matrix. The second step is composition defined as Bk′=A′∘Rk, and the third one is aggregation defined as B′=⋃k=1rBk′.Furthermore, the SIRI implication has two more substeps. The first substep is sorting program. The matrixCk is generated as (43)Ck=a1ka2k⋯ankb1kb2k⋯bmk1.11.2⋯1.n2.12.2⋯2.m2×(n+m),where the elements in the first row of (43) are the combination of Ak and Bk with Ak=[a1k,a2k,…,ank],Bk=[b1k,b2k,…,bmk]. In addition, the second row of (43) has two arguments for every cell in the first row, and the first argument could be “1” or “2” depending on the cell of the first row belonging to Ak or Bk, respectively. Moreover, the second argument of the second row in (43) could be ank or bmk; that is, a1k=b1k=1, a2k=b2k=2,…, and ank=n, bmk=m, where ank and bmk belong to Ak and Bk, respectively.Sort the matrixCk based on the 1st row and obtained as(44)Ck=quicksortCk,1strow.After taking the Quicksort algorithm, the final Ck is sorted as (45)Ck=c1kc2k⋯cn+mk⋯⋯⋯xn+myn+m2×(n+m),where c1k is minimum of the 1st row and cn+mk is maximum of the 1st row and xn+m is 1 or 2 to indicate the value cn+mk belonging to Ak or Bk, respectively. yn+m in (45) is used to define the position of the value cn+mk in Ak or Bk depending on xn+m which is 1 or 2, respectively. The second substep is getting relational matrix, which has n+m steps. In the first step, let us consider the condition of xn+m as ifxn+m=1, then all values in the yn+mth row of Rk are equal to cn+mk;ifxn+m=2, then all values in the yn+mth column of Rk are equal to cn+mk.In the next step, consider the condition ofxn+m-1, and keep on the algorithm until x1.(3) IRI and SIRI Schemes. The main IRI operation is “calculating relational matrix” and the main operation of the SIRI belongs to “sorting program.” The operation schemes of IRI and SIRI are listed in Table 8.Table 8
IRI and SIRI schemes.
IRI
SIRI
Implication
Implication
Cylindrical extension
Sorting program
Calculating relational matrix
Getting relational matrix
Composition
Composition
Aggregation
Aggregation(4) Time Complexity. The comparison results are shown in Table 9. Three parameters r, n, and m and Quicksort are used for the SIRI sorting program to verify the time complexity. The time complexity of an array with n+m elements is On+mlog⁡2n+m which can be determined from Theorem 1 again. With SISO r-rule fuzzy systems, the time complexity of the implication step of SIRI method is(46)Orn+mlog⁡2n+m.Table 9
Comparison of the time complexity of IRI and SIRI.
IRI time complexity (min operations)
SIRI time complexity (min operations)
Implication
O
(
r
n
m
)
O
r
n
+
m
log
2
⁡
(
n
+
m
)Furthermore, the time complexity of the implication step of IRI method can be obtained from (40) and expressed as(47)Ornm.In order to understand the operation complexity of these methods, the results from time complexity comparison are shown in Figure5. The input dimension is considered equal to the output dimension. The number of rules is set to 10. Red line (curve for IRI) shows the relation of x (dimension of input and output) and y (operations). On the contrary, the blue line (dash curve for SIRI) represents the relation of x (dimension of input and output) and y (operations). On the other hand, the green line is a reference line which with the input dimension is 50 and the output dimension is 50. Red point, at the red line with input dimension = 50, output dimension = 50, number of rules = 10, shows operations of IRI=25000 operations. Blue point, at the blue line with input dimension = 50, output dimension = 50, and number of rules = 10, showed operations of SIRI=6644 operations. As previously described, it is clear that the IRI operations are definitely larger than the SIRI operations.Figure 5
IRI and SIRI implication step time complexity comparison results withr=10, n=m.(5) Space Complexity. In this subsection, the space complexity of the SIRI implication step is shown. This is an improvement in the IRI implication step. In Table 10, the space complexity of IRI and SIRI is illustrated with the r, n, and m parameters again. By taking account of every relational matrix into (40), the space complexity of O(nm) is for IRI; on the contrary, with SISO r rules the IRI requires space of O(rnm).Table 10
IRI and SIRI space complexity comparison.
IRI
space complexity
(cells)
SIRI
space complexity
(cells)
Implication
1 relation matrix
O
(
n
m
)
1 relation matrix
O
(
n
+
m
)
r relation matrixes
O
(
r
n
m
)
r relation matrixes
O
(
r
n
m
)Based on (44) for every relational matrix, SIRI just needs a space of O(n+m) but applying (40) IRI needs a space of O(nm).


## 2.2.1. The Comparison of CRI and IRI

(1) CRI and IRI Schemes. In order to achieve a meaningful inference result based on Zadeh’s compositional rule of inference (CRI) [2], for a given system observation there are two basic methods adopted as important illustrations. The first one is called CRI or FATI (first aggregate then infer) [3]. In this first method, for a given observation of A′, the implication is the first step performed to calculate the relational matrix given as (16)Rk=IAk,Bk,where Rk is the fuzzy implication relation for rule k and I denotes the implication method. All of the rules are then aggregated by structuring an overall fuzzy relation R which is the combination of all relational matrixes and written as(17)R=⋃k=1rRk,where R indicates an overall fuzzy relation and ∪ is defined as a combination operator of all the fuzzy implication relations. The last equation is with a final result based on a given observation A′ and shown as(18)B′=A′∘R,where ∘ represents composition within the CRI context and B′ is an inference result.The second one is called individual rule-based inference (IRI) or FITA (first infer then aggregate) [3]. For a given observation A′, we first perform the implication step to calculate the relational matrix as follows:(19)Rk=IAk,Bk,where Rk denotes the fuzzy implication relation for rule k and I is the implication method.A result for every rule based on a given observationA′ is then inferred as (20)Bk′=A′∘Rk,where Bk′ is the inference result based on rule k. Finally, all of these intermediate results are combined and determined as(21)B′=⋃k=1rBk′.Table2 showed the CRI and IRI schemes.Table 2
CRI and IRI schemes.
CRI
IRI
Step1
Implication
Implication
Step2
Aggregation
Composition
Step3
Composition
Aggregation(2) Time Complexity. In Table 3, r represents the number of rules, n is the number of elements in the input, and m indicates the number of elements in the output. Assume that minimum and maximum operations require the same effort. Applying (16) to each rule, every Rk requires nm operations and results in the implication step with r rules requires rnm operations. Based on (17), the aggregation of r relation matrixes requires r-1nm operations. The CRI composition requires nm operations for intersection and (n-1)m operations for projection. Both intersection and projection are calculated using (18). To infer a conclusion from a SISO r rules with CRI method, the total time can be easily determined as(22)tCRI=rnm+r-1nm+nm+n-1m,where tCRI denotes the CRI method time complexity. Using the result for every rule based on a given observation shown in (19), the IRI implication requires nm operations for every relational matrix Rk, and so with r relational matrixes it is just rnm operations. The IRI composition requires rnm operations for intersection and r(n-1)m operations for projection. Both intersection and projection are calculated using (20).Table 3
CRI and IRI time complexity comparison.
CRItime complexity(operations)
IRItime complexity(operations)
(1) Implication
r
n
m
r
n
m
(2) Aggregation (CRI)
r
-
1
n
m
(3) Composition
Intersection
n
m
r
n
m
Projection
n
-
1
m
r
n
-
1
m
(4) Aggregation (IRI)
r
-
1
m
Total time
r
n
m
+
r
-
1
n
m + nm+n-1m
r
n
m
+
r
n
m + rn-1m + r-1mAdopting (21), the IRI aggregation of r conclusions Bk′ will obtain r-1m operations. A conclusion from SISO r rules can be derived with the IRI method, with the total time measured as (23)tIRI=rnm+rnm+rn-1m+r-1m,where tIRI is the IRI method time complexity.The advantage of CRI compares to IRI in SISO rules expressed analytically in terms of gainG as(24)G=tIRItCRI.By substituting (22) and (23) into the last equation, the gain becomes (25)G=tIRItCRI=2rnm+rn-1m+r-1mrnm+r-1nm+nm+n-1m=3rn-12rn+n-1≈32>1.The formula shows that gainG is always bigger than 1. We pointed out that the CRI method time complexity is less than the IRI method time complexity in the SISO rules expert system.(3) Space Complexity. In Table 4, the same definition expressed in Table 3 is used for r, n, and m, assuming that every element requires one cell. Applying (16) to each rule, each Rk requires nm cells and results in the implication step with r rules requires rnm cells. Based on (17), it is clear that the aggregation of r relation matrix requires nm cells. Using (18), it is known that the composition of CRI requires nm cells for intersection and m cells for projection, respectively. In general, to infer a conclusion from SISO r rules with the CRI method, the required space is determined using the biggest space from all steps and obtained as (26)Ornm.Table 4
CRI and IRI space complexity comparison.
CRI space complexity (cells)
IRI space complexity (cells)
(1) Implication
r
n
m
r
n
m
(2) Aggregation (CRI)
n
m
(3) Composition
Intersection
n
m
r
n
m
Projection
m
r
m
(4) Aggregation (IRI)
m
The biggest space of all steps
r
n
m
r
n
mTo determine the implication that IRI requiresnm cells for every relational matrix Rk using (19), that is, with r, relational matrixes rnm cells are necessary. Based on (20), the IRI composition requires rnm cells for intersection and rm cells for projection, respectively. Therefore, with (21) the aggregation of r conclusions Bk′ requires m cells. Hence, to infer a conclusion from SISO r rules with the IRI method, the required space can be determined using the biggest space from all steps and written as(27)Ornm.For the purpose of optimization, CRI combines step (1) (implication) with step (2) (aggregation); thus, it is easily understood that CRI needs a space ofO(nm). IRI requires a space of O(rnm) to store r relational matrixes in the implication step. It is worth noting that the CRI method space complexity is less than the IRI method space complexity in the SISO rules expert system.


## 2.2.2. CRI and SCRI

(1) CRI. As mentioned in Section 2.2.1(1) the first CRI method step is the implication step, which includes two substeps. The first substep is cylindrical extension defined as(28)Ak_ex=a11ka12k⋯a1mka21ka22k⋯a2mk⋮⋮⋯⋮an1kan2k⋯anmkn×m,where Ak_ex is extended by Ak, aijk=aik, with Ak=[aik]i=1n,i=1,2,…,n,j=1,2,…,m,k=1,2,…,r: (29)Bk_ex=b11kb12k⋯b1mkb21kb22k⋯b2mk⋮⋮⋯⋮bn1kbn2k⋯bnmkn×m,where Bk_ex is extended by Bk, bijk=bjk, with Bk=[bjk]j=1m, i=1,2,…,n, j=1,2,…,m, k=1,2,…,r.Filling all of the columns in the related matrix using theX-projection is cylindrical extension from X-projection which is shown in (28). Similarly, cylindrical extension from Y-projection means filling all of the rows in the relation matrix using the Y-projection as shown in (29). Calculating relation matrix is the second substep to be defined and it is written as(30)Rk=min⁡Ak_ex,Bk_ex=q11kq12k⋯q1mkq21kq22k⋯q2mk⋮⋮⋯⋮qn1kqn2k⋯qnmkn×m,where Rk is the relation matrix for rule k and qijk=min⁡(aijk,bijk), i=1,2,….,n; j=1,2,…,m. The implication is “min” as Mamdani fuzzy model. Aggregation, the second CRI method step, is defined as(31)R=⋃k=1rRk,where R is the overall relation matrix, which is calculated by combining all of the relation matrix Rk with k=1,2,…,r. Composition is the final CRI step and it is defined as (see Appendix B)(32)B′=A′∘R=sup⁡min⁡A′_ex,R=sup⁡b11′b12′⋯b1m′b21′b22′⋯b2m′⋮⋮⋯⋮bn1′bn2′⋯bnm′n×m=b1′b2′⋯bm′,where A′_ex is extended by A′,B′ is the inference result which is calculated by compositing the observation A′ with the overall relational matrix R, and ∘ represents the composition method.(2) SCRI (Sort CRI). In this subsection, the SCRI method is introduced. It includes three steps. The first step is implication which has two substeps. The first substep is sorting program and the second substep is getting relational matrix. The second step is aggregation defined as R=⋃k=1rRk. Composition is the third step and given as B′(v)=A′∘R=sup⁡min⁡A′_ex,R, where A′_ex is extended by A′. Moreover, let us discuss the SCRI method implication step in detail. The SCRI implication has two substeps. The matrix Ck is necessary for processing the first sorting program step, which can be expressed as(33)Ck=a1ka2k⋯ankb1kb2k⋯bmk1.11.2⋯1.n2.12.2⋯2.m2×(n+m),where the elements in the first row of (33) are a combination of Ak and Bk with Ak=[a1k,a2k,…,ank],Bk=[b1k,b2k,…,bmk]. In addition, the second row of (33) has two arguments for every cell in the first row. The first argument could be “1” or “2” depending on whether the cell in the first row belongs to Ak or Bk, respectively. Moreover, the second argument for the second row in (33) could be ank or bmk; that is, a1k=b1k=1,a2k=b2k=2,…, and ank=n, bmk=m, where ank and bmk belong to Ak and Bk, respectively.To sort the matrixCk based on the 1st row is the second step which is obtained as (34)Ck=quicksortCk,1strow.The Quicksort algorithm then sorts theCk as(35)Ck=c1kc2k⋯cn+mk⋯⋯⋯xn+myn+m2×(n+m),where c1k is minimum of the 1st row, cn+mk is maximum of the 1st row, and xn+m is 1 or 2 to indicate that the value cn+mk belongs to Ak or Bk, respectively. yn+m in (35) is used to specify the position of the value cn+mk in Ak or Bk depending on whether xn+m is 1 or 2, respectively. The second substep is getting relational matrix, which has n+m steps. In the first step, consider the condition of xn+m asifxn+m=1, then all values in the yn+mth row of Rk are equal to cn+mk;ifxn+m=2, then all values in the yn+mth column of Rk are equal to cn+mk.In the second step, consider the condition of xn+m-1, and keep on continuing until x1.(3) CRI and SCRI Schemes. Table 5 showed the CRI and SCRI schemes. In the implication step, the main CRI operation is “calculating relational matrix” and the main SCRI operation is “sorting program.”Table 5
CRI and SCRI schemes.
CRI
SCRI
Implication
Implication
Cylindrical extension
Sorting program
Calculating relational matrix
Getting relational matrix
Aggregation
Aggregation
Composition
Composition(4) Time Complexity. SCRI is an improvement method from correcting the CRI implication step. The time complexity of the implication step for these two methods is compared and the results are shown in Table 6. The same r, n, and m parameters and the Quicksort are adopted for the SCRI sorting program. Following Theorem 1, the time complexity of an array with n+m elements is On+mlog2n+m. With SISO r-rule fuzzy system, the time complexity of the implication step of SCRI method is denoted as(36)Orn+mlog2n+m.Based on (30), the time complexity of the implication step for CRI method can be determined as(37)Ornm.Table 6
CRI and SCRI time complexity comparison results.
CRI time complexity (min operations)
SCRI time complexity (min operations)
Implication
O
(
r
n
m
)
O
r
n
+
m
log
2
⁡
n
+
mThe input dimension equals the output dimension in Figure4 and the number of rules is 10. The red line (curve for CRI) shows the relation of x (dimension of input and output) and y (operations), and the blue line (dash curve for SCRI) shows the relation of x (dimension of input and output) and y (operations), respectively. Moreover, the green line shows a reference line with the input dimension as 40 and the output dimension as 40. The red point in the red line with input dimension = 40, output dimension = 40, and the number of rules = 10 shows CRI=16000 operations. The blue point at the blue line with input dimension = 40, output dimension = 40, and number of rules = 10 shows SCRI=5058 operations. It is clear to see that the CRI method time complexity is greater than the SCRI method time complexity.Figure 4
CRI and SCRI implication step time complexity comparison withr=10, n=m.(5) Space Complexity. In this subsection SCRI is discussed as an improvement in the CRI implication step. The implication step space complexity of the CRI and SCRI methods is shown in Table 7. By substituting r, n, and m of the output elements into (30) for every relational matrix, the CRI needs a space of O(nm). With SISO r rules the CRI needs a space of O(rnm). Thus, based on (34), for every relational matrix, it is known that SCRI needs a space of O(n+m). With SISO r rules, SCRI needs a space of O(rnm) to store r relational matrixes.Table 7
CRI and SCRI space complexity comparison.
CRI
space complexity
(cells)
SCRI
space complexity
(cells)
Implication
1 relation matrix
O
(
n
m
)
1 relation matrix
O
(
n
+
m
)
r relation matrixes
O
(
r
n
m
)
r relation matrixes
O
(
r
n
m
)Based on (34), for every relational matrix, SCRI just needs a space of O(n+m) but applying (30) CRI needs a space of O(nm).


## 2.2.3. IRI and SIRI

(1) IRI. The first step in the IRI method is the implication step as defined in Section 2.2.1(1), which includes two substeps. The first substep is cylindrical extension defined as(38)Ak_ex=a11ka12k⋯a1mka21ka22k⋯a2mk⋮⋮⋯⋮an1kan2k⋯anmkn×m,where Ak_ex is extended by Ak, aijk=aik, with Ak=[aik]i=1n, i=1,2,…,n, j=1,2,…,m, k=1,2,…,r:(39)Bk_ex=b11kb12k⋯b1mkb21kb22k⋯b2mk⋮⋮⋯⋮bn1kbn2k⋯bnmkn×m,where Bk_ex is extended by Bk, bijk=bjk, with Bk=[bjk]j=1m, i=1,2,…,n, j=1,2,…,m, k=1,2,…,r.The second substep is calculating relation matrix defined as(40)Rk=min⁡Ak_ex,Bk_ex,where Rk is the relation matrix of rule k. The implication is “min” as Mamdani fuzzy model. The second step of IRI method is composition which is defined as(41)Bk′=A′∘Rk,where Bk′ is the inference result of rule k and it is calculated by composing observation A′ with the relational matrix Rk of rule k and ∘ represents the composition method. The third step of IRI is aggregation defined as(42)B′=⋃k=1rBk′,where B′ is the final inference result. It is calculated by combining all of the inference results Bk′ with k=1,2,…,r.(2) SIRI (Sort IRI). Containing three steps for SIRI method, the first step is implication which involves two substeps. The first substep is sorting program and the second substep is getting relational matrix. The second step is composition defined as Bk′=A′∘Rk, and the third one is aggregation defined as B′=⋃k=1rBk′.Furthermore, the SIRI implication has two more substeps. The first substep is sorting program. The matrixCk is generated as (43)Ck=a1ka2k⋯ankb1kb2k⋯bmk1.11.2⋯1.n2.12.2⋯2.m2×(n+m),where the elements in the first row of (43) are the combination of Ak and Bk with Ak=[a1k,a2k,…,ank],Bk=[b1k,b2k,…,bmk]. In addition, the second row of (43) has two arguments for every cell in the first row, and the first argument could be “1” or “2” depending on the cell of the first row belonging to Ak or Bk, respectively. Moreover, the second argument of the second row in (43) could be ank or bmk; that is, a1k=b1k=1, a2k=b2k=2,…, and ank=n, bmk=m, where ank and bmk belong to Ak and Bk, respectively.Sort the matrixCk based on the 1st row and obtained as(44)Ck=quicksortCk,1strow.After taking the Quicksort algorithm, the final Ck is sorted as (45)Ck=c1kc2k⋯cn+mk⋯⋯⋯xn+myn+m2×(n+m),where c1k is minimum of the 1st row and cn+mk is maximum of the 1st row and xn+m is 1 or 2 to indicate the value cn+mk belonging to Ak or Bk, respectively. yn+m in (45) is used to define the position of the value cn+mk in Ak or Bk depending on xn+m which is 1 or 2, respectively. The second substep is getting relational matrix, which has n+m steps. In the first step, let us consider the condition of xn+m as ifxn+m=1, then all values in the yn+mth row of Rk are equal to cn+mk;ifxn+m=2, then all values in the yn+mth column of Rk are equal to cn+mk.In the next step, consider the condition ofxn+m-1, and keep on the algorithm until x1.(3) IRI and SIRI Schemes. The main IRI operation is “calculating relational matrix” and the main operation of the SIRI belongs to “sorting program.” The operation schemes of IRI and SIRI are listed in Table 8.Table 8
IRI and SIRI schemes.
IRI
SIRI
Implication
Implication
Cylindrical extension
Sorting program
Calculating relational matrix
Getting relational matrix
Composition
Composition
Aggregation
Aggregation(4) Time Complexity. The comparison results are shown in Table 9. Three parameters r, n, and m and Quicksort are used for the SIRI sorting program to verify the time complexity. The time complexity of an array with n+m elements is On+mlog⁡2n+m which can be determined from Theorem 1 again. With SISO r-rule fuzzy systems, the time complexity of the implication step of SIRI method is(46)Orn+mlog⁡2n+m.Table 9
Comparison of the time complexity of IRI and SIRI.
IRI time complexity (min operations)
SIRI time complexity (min operations)
Implication
O
(
r
n
m
)
O
r
n
+
m
log
2
⁡
(
n
+
m
)Furthermore, the time complexity of the implication step of IRI method can be obtained from (40) and expressed as(47)Ornm.In order to understand the operation complexity of these methods, the results from time complexity comparison are shown in Figure5. The input dimension is considered equal to the output dimension. The number of rules is set to 10. Red line (curve for IRI) shows the relation of x (dimension of input and output) and y (operations). On the contrary, the blue line (dash curve for SIRI) represents the relation of x (dimension of input and output) and y (operations). On the other hand, the green line is a reference line which with the input dimension is 50 and the output dimension is 50. Red point, at the red line with input dimension = 50, output dimension = 50, number of rules = 10, shows operations of IRI=25000 operations. Blue point, at the blue line with input dimension = 50, output dimension = 50, and number of rules = 10, showed operations of SIRI=6644 operations. As previously described, it is clear that the IRI operations are definitely larger than the SIRI operations.Figure 5
IRI and SIRI implication step time complexity comparison results withr=10, n=m.(5) Space Complexity. In this subsection, the space complexity of the SIRI implication step is shown. This is an improvement in the IRI implication step. In Table 10, the space complexity of IRI and SIRI is illustrated with the r, n, and m parameters again. By taking account of every relational matrix into (40), the space complexity of O(nm) is for IRI; on the contrary, with SISO r rules the IRI requires space of O(rnm).Table 10
IRI and SIRI space complexity comparison.
IRI
space complexity
(cells)
SIRI
space complexity
(cells)
Implication
1 relation matrix
O
(
n
m
)
1 relation matrix
O
(
n
+
m
)
r relation matrixes
O
(
r
n
m
)
r relation matrixes
O
(
r
n
m
)Based on (44) for every relational matrix, SIRI just needs a space of O(n+m) but applying (40) IRI needs a space of O(nm).


## 3. Conclusion

The SCRI and SIRI schemes for improving CRI and IRI operation performance for the fuzzy control theoretical approach are proposed in this paper. The previous methods were proven to reduce the time and space complexity for fuzzy expert systems by improving the most important step (implication). It was shown that the time consuming, for example, the implication step, needs an operation ofO(n×m), in the traditional methods with compositional rule-based inference (CRI) and individual rule-based inference (IRI) will be significantly decreased as O(n+m)log⁡2(n+m). With SISO multirule systems the two SCRI and SIRI schemes are proven to perform much better than CRI and IRI in time and space complexity. This paper generated better SCRI (Sort CRI) and SIRI (Sort IRI) performance in which two can replace the traditional CRI and IRI using the Mamdani implication, respectively. We are going to extend these results for MISO and MIMO fuzzy systems in the future works.



---

*Source: 725258-2015-03-26.xml*