ABSTRACT
In this thesis, we have studied the concept of compatibility relation and construction of an algorithm
for determining maximal compatibility classes. We have identified some new characteristic
properties of compatibility classes and constructed an alternative algorithm for computing maximal
compatibility classes. Finally, we have described the concept of how maximal compatibility classes
help in segmentation and decentralization of switched networks.
TABLE OF CONTENTS
Title page……………………………………………………………………………………………..i
Declaration……………………………………………………….………………………………..ii
Certification………………………………………………………………………………….……iii
Dedication…………………………………………………………………………………………iv
Acknowledgement…………………………………………………………………………………v
Abstract………………………………………………………………………………………….vii
Content……………………………………………………………………………………….….viii
1 Introduction 1
1.1 Background of the study……………………………..………………………….……………..1
1.2 Statement of the problem…………………………………………..…………………………..3
1.3 Motivation for the Research…….…………………………………………………..…………3
1.4 Objectives of the Research……………………………..………………………..….………….3
1.5 Methodology……….…………………………………………………………………………..3
1.6 Organization of the thesis…………………..….…………………………………………..….3
2 Literature Review 5
2.1 Literature Review……………………………………………………..……………………….5
2.2 Binary Relations and Their Properties….………………………….………………………….9
2.3 Definition………………………………………………………………………………………..9
2.4 Types of Relation………………………………………………………….…………………10
ix
2.5 Power of Relation……………………………………………………….……………….……12
2.6 Representation of Relation ……………………………………………………………………13
2.7 Matrix Representation of Relation…………………………………………………………….13
2.8 Graphical Representation of Relation………………………………………………………..15
2.9 Representing Relation using Sagittal diagram….……….……………………………………16
3 Compatibility Relation and Some related Concepts 19
3.1 Compatibility Relation and Some related Concepts…………………………………………19
3.2 Compatibility Relation……………………………………………………………………….19
3.3 Characteristic Properties of Compatibility Classes………………………………………… 23
3.4 Concept of Compatibles in Sequential Machines…………………………………………….26
3.5 Maximal Compatible Chart………………………………………………………………….28
3.6 Relation matrix of a Compatibility Relation and Construction of an algorithm to compute MCC
……………………………………………………………………………………………..32
3.7 Algorithm to compute MCCs from CMCCs…………………………………………….……33
4 Application of Compatibility Relation to Switched Networks 44
4.1 Introduction………………………………………………………………………………….. 44
4.2 Some Definitions..……..……………………………………………………..…………….. 44
4.3 Throughputs………………………………………..…………………………………………46
4.3.1 Maximum theoretical throughput……………………………………………….………….47
x
4.3.2 Peak measured throughput……………………………….…………………………………47
4.3.3 Maximum sustained throughput …………..……………………….…………………….. 48
4.4 Concept of Switching…………………………………………………………………………49
4.4.1 Switches in Network………………………………………………………………………………………………50
4.4.2 Network Congestion……………………………………..…………………………….…..51
4.4.3 Network Segmentation…………………………………………………………….….……51
4.4.4 Limitation of Network Segmentation Method (NSM)……………………….………………52
4.4.5 Application of Compatibility Relation to Switched Network………………………………52
4.4.6 Compatibility Relation based segmentation procedure…………………………………….53
4.5 Network Decentralization……………………………………………………………………59
4.5.1 Some Basic Definitions……………………………………………………………………59
4.5.2 The Structure of a Decentralized Network…………………………………………………60
4.5.3 Limitations of a Decentralized Network……………………………………………………61
4.5.4 Application of the notion of maximal compatibles in network decentralization………..…62
4.5.5 Some Characteristics of Compatibility based Decentralized Network…………………….63
5 Conclusion and Future direction 65
5.1 Conclusion…………………………………………..……………………………………….65
5.2 Recommendations……………………………………………………………………………65
References………………………………………………………………………………………..67
xi
List of Figures and Tables
1. Figure 2.1: graphical representation of relation.
2. Figure 2.2: representation of reflexive and symmetric relation.
3. Figure 2.3: graphical representation of reflexive, symmetric and transitive relation.
4. Figure 2.4: sagittal diagram.
5. Figure 3.1: compatibility graph.
6. Figure 3.2: simplified graph of a compatibility relation.
7. Table IA: flow table.
8. Table IB: compatibility chart.
9. Table II: maximal compatibility chart.
10. Table III: maximal compatibility chart.
11. Table IVA: compatibility chart.
12. Table IVB: maximal compatibility chart.
13. Table A: compatibility table.
14. Table B: compatibility table representing CMCCs and MCCs.
15. Table C: compatibility table.
16. Table 1: compatibility table.
17. Table 2: compatibility table.
18. Table 3: compatibility table.
19. Table A1: compatibility table.
20. Table B1: compatibility table.
21. Figure 4.1: OSI model.
22. Figure 4.2: OSI model implementation diagram.
23. Figure 4.3: switches in network.
xii
24. Figure 4.4: unsegmented network.
25. Figure 4.5: segmented network.
26. Figure 4.6: compatibility based segmentation procedure.
27. Figure 4.7: compatibility graph.
28. Figure 4.8: diagram representing links and queues.
29. Figure 4.9: star topology.
30. Figure 4.10: mesh topology.
31. Figure 4.11: graph of R1.
32. Figure 4.12: graph of R2.
33. Figure 4.13: decentralized network organized as middleware.
1
CHAPTER ONE
INTRODUCTION
1.1 Background of the study
It is difficult to trace since when the profound mathematics of compatibility relation came into
existence. To our knowledge, Kurepa (1952- 1953) seems to be the earliest full- blown mathematical
exposition on the study of reflexive symmetric relations and graphs. Since then, a number of works
(Paull and Unger, 1959; William, 1962; McCluskey, 1962; Weissman, 1962; Grasselli (1962, 1965,
1966); Hill and Peterson, 1968; Kohavi, 1978; Pognowski, 1981; Chakraborty, 1987; Biswas, 1989;
Yager, 1990; Yen, 1990; Zhao et al., 1997; Singh and William-west, 2012; etc.), dealing with
fundamentals of compatibility relation as well as its applications has appeared.
As of now, it can be said that the actual import of compatibility relation has gone far beyond its
ordinary linguistic connotation and even that of its mathematical characterization. It has found
several applications in different fields of knowledge. Essentially, from application points of view,
compatibility relation is useful in solving a class of minimization problems, particularly when the
problems are incompletely specified:
(a) In switching theory, particularly for incompletely specified problems (McCluskey,
(1962); Singh and William-west, (2012));
(b) In incompletely specified sequential networks for reduction of the number of
internal states (Charkraborty, 1987);
(c) In designing of a class of digital control Units (Grasselli, 1962);
(d) In graph theory ( Hills and Peterson, 1968);
(e) In solving some combinatorial problems, such as scheduling of traffic control
(Grasselli, 1966);
(f) In phonology (Pognowski, 1981);
2
just to mention a few, (see (Grasselli, 1962) for some further details).
Further, the notion of compatibility relation has been used in augmenting the theory of
evidence(Dempster- Shafer Structure, in particular) where generalized compatibility relation is
combined, based on possibility theory to extend Dempster’ rule (Yen, 1990).
Also, the application of compatibility relation is made in deriving inference about one variable, based
upon the knowledge about another variable, in Belief structure (Yager, 1990).
In recent years, some application of compatibility relation can be found in defining Tolerance
multisetsin (Pognowski, 1981), Tolerance rough sets in (Lipovaski, 1994) and Symmetrized Maxplus
Algebra (Singh et al., 2010), etc.
In fact, compatibility relation is known to have a number of applications in Computer science. For
example, in a sequential circuit, when redundant states need to be removed to minimize failures,
particularlywhen the number of memory elements is directly related to the number of states,
compatibility relation is used (Zhao et al., 1997).
Usually, in applications of compatibility relation, such as state minimization of incompletely
specified sequential machines (ISSM), it is required to derive the set of all maximal compatibility
classes of a finite set endowed with a compatibility relation. To derive these classes for an - set,
when is relatively small; it can be obtained by means of a compatibility diagram. However, for a
large , determining maximal compatibility classes by means of diagrams becomes difficult to
visualize. Moreover, in order to compute maximal compatibility classes, a diagrammatic
representation would not suffice because computers are not good at viewing pictures, etc. In view of
this, a necessity to have an algorithm arises. Consequent to this, to our knowledge, an algorithm for
determining the maximal compatibility classes of a compatibility relation was first presented in
(Grasselli, 1966) and recently, in (Biswas, 1989).
3
1.2 Statement of the Problem
This research work endeavours to identify some new properties of compatibility classes of a finite set
on which a suitable compatibility relation is defined, construct an alternative algorithm to compute
maximal compatibility classes and demonstrate their applications in solving decentralization
problems of a switched network.
1.3 Motivation for the Research
In view of having found numerous applications of a compatibility relation in different fields, in
particular, that of maximal compatibility classes, we found it significant to study and examine its
applications to a switched network.
1.4 Objectives of the Research
The main objective of this research is to construct an alternative algorithm to compute maximal
compatibility classes of a compatibility relation defined on a finite set, and apply it to a switched
network.
1.5 Methodology
The exploratory research approach is adopted in this study. A survey of the works on compatibility
relation and its application will be conducted, properties of compatibility classes will be identified,
and an alternative algorithm to compute maximal compatibility classes will be constructed. The data
used in this research work is largely gathered from published academic works on this subject.
1.6 Organization of the Thesis
The thesis is organized as follows:
Besides the background of the study, objective of the research and methodology given in chapter
one, chapter two provides a detailed literature review on the subject matter.
4
Chapter three provides some fundamentals of the theory of relations, mathematics of compatibility
relation, characteristic properties of maximal compatibility classes and an algorithm to compute
them.
Chapter four presents an application of compatibility relation to a switched network.
Chapter five gives conclusion and recommendations.
5
Do you need help? Talk to us right now: (+234) 08060082010, 08107932631 (Call/WhatsApp). Email: [email protected].
IF YOU CAN'T FIND YOUR TOPIC, CLICK HERE TO HIRE A WRITER»
