## 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»**