# Quotient Space Based Problem Solving

**A Theoretical Foundation of Granular Computing**

**By**

- Ling Zhang, Professor, Department of Computer Science at Anhui University in Hefei, China
- Bo Zhang, Professor, Computer Science and Technology Department at Tsinghua University in Beijing, China

### Audience

Quotient Space Based Problem Solving is designed for graduate students, research fellows and technicians in Computer Science, especially Artificial Intelligence, and those concerned with computerized problem solving.

### Book information

- Published: February 2014
- Imprint: MORGAN KAUFMANN
- ISBN: 978-0-12-410387-0

### Reviews

"... aimed primarily at graduate students (and academicians) with strong mathematical maturity and an interest in mathematical modeling in the fields around artificial intelligence (AI)."

### Table of Contents

Preface

Chapter 1 Problem Representation

1. Problem Solving

2. World Representations at Different Granularities

2.1 The Model of Different Grain-size Worlds

2.2 The Definition of Quotient Space

3. The Acquisition of Different Grain-size Worlds

3.1 The Granulation of Domain

3.2 The Granulation by Attributes

3.3 The Granulation of Structures

4. The Relations among Different Grain-size Worlds

4.1 The Structure of Multi-granular Worlds

4.2 The Structural Completeness of Multi-granular Worlds

5. Property Preserving Ability

5.1 Falsity-Preserving Principle

5.2 Quotient Structure

6. Selection and Adjustment of Grain-sizes

6.1 Mergence Methods

6.2 Decomposition Methods

6.3 The Existence and Uniqueness of Quotient Semi-order

6.4 The Geometrical Interpretation of Mergence and Decomposition Methods

7. Conclusions

Chapter 2 Hierarchy and Multi-granular Computing

2.1 The Hierarchical Model

2.2 The Estimation of Computational Complexity

2.2.1 The Assumptions

2.2.2 The Estimation of Computational Complexity under Deterministic Models

2.2.3 The Estimation of Computational Complexity under Probabilistic Models

2.2.4 The Successive Operation in Multi-granular Computing

2.3 The Extraction of Information on Coarsely Granular Levels

2.3.1 Examples

2.3.2 Constructing under Unstructured Domains

2.3.3 Constructing under Structured Domains

2.3.4 Conclusions

2.4 Fuzzy Equivalence Relations and Hierarchy

2.4.1 The Properties of Fuzzy Equivalence Relations

2.4.2 The Structure of Fuzzy Quotient Spaces

2.4.3 Cluster and Hierarchical Structure

2.4.4 Conclusions

2.5 The Applications of Fuzzy Quotient Space Theory

2.5.1 Introduction

2.5.2 The Structural Definition of Fuzzy Sets

2.5.3 The Robustness of the Structural Definition of Fuzzy Sets

2.5.4 Conclusions

2.6 Conclusions

Chapter 3 Information Synthesis in Multi-granular Computing

3.1 Introduction

3.2 The Mathematical Model of Information Synthesis

3.3 The Synthesis of Domains

3.4 The Synthesis of Topologic Structures

3.5 The Synthesis of Semi-order Structures

3.5.1 The Graphical Constructing Method of Quotient Semi-order

3.5.2 The Synthesis of Semi-order Structures

3.6 The Synthesis of Attribute Functions

3.6.1 The Synthetic Principle of Attribute Functions

3.6.2 Examples

3.6.3 Conclusions

Chapter 4 Reasoning in Multi-granular Computing

4.1 Reasoning Models

4.2 The Relation between Uncertainty and Granularity

4.3 Reasoning (Inference) Networks (1)

4.3.1 Projection

4.3.2 Synthesis

4.3.3 Experimental Results

4.4 Reasoning Networks (2)

4.4.1 Modeling

4.4.2 The Projection of AND/OR Relations

4.4.3 The Synthesis of AND/OR Relations

4.4.4 Conclusions

4.5 Operations and Quotient Structures

4.5.1 The Existence of Quotient Operation

4.5.2 The Construction of Quotient Operations

4.5.3 The Approximation of Quotient Operations

4.5.4 Constraints and Quotient Constraints

4.6 Qualitative Reasoning

4.6.1 Qualitative Reasoning Models

4.6.2 Examples

4.6.3 The Procedure of Qualitative Reasoning

4.7 Fuzzy Reasoning based on Quotient Space Structures

4.7.1 Fuzzy Set based on Quotient Space Model

4.7.2 Fuzzified Quotient Space Theory

4.7.3 The Transformation of Three Granular Computing Methods

4.7.4 The Transformation of Probabilistic Reasoning Models

4.7.5 Conclusions

Chapter 5 Automatic Spatial Planning

5.1 Automatic Generation of Assembly Sequences

5.1.1 Introduction

5.1.2 Algorithms

5.1.3 Examples

5.1.4 Computational Complexity

5.1.5 Conclusions

5.2 The Geometrical Methods of Motion Planning

5.2.1 Configuration Space Representation

5.2.2 Finding Collision-free Paths

5.2.3 Conclusions

5.3 The Topological Model of Motion Planning

5.3.1 The Mathematical Model of Topology Based Problem Solving

5.3.2 The Topological Model of Collision-free Paths Planning

5.4 Dimension Reduction Method

5.4.1 Basic Principle

5.4.2 Characteristic Network

5.5 Applications

5.5.1 The Collision-free Paths Planning for a Planar Rod

5.5.2 Motion Planning for a Multi-joint Arm

5.5.3 The Applications of Multi-granular Computing

5.5.4 The Estimation of the Computational Complexity

Chapter 6 Statistical Heuristic Search

6.1 Statistical Heuristic Search

6.1.1 Heuristic Search Methods

6.1.2 Statistical Inference

6.1.3 Statistical Heuristic Search

6.2 The Computational Complexity

6.2.1 SPA Algorithms

6.2.2 SAA Algorithms

6.2.3 Different Kinds of SA6.2.4 The Successive Algorithms

6.3 The Discussion of Statistical Heuristic Search

6.3.1 Statistical Heuristic Search and Quotient Space Theory

6.3.2 Hypothesis I

6.3.3 The Extraction of Global Statistics

6.3.4 SA Algorithms

6.4 The Comparison between Statistical Heuristic Search and A* Algorithm

6.4.1 Comparison to A*

6.4.2 Comparison to Other Weighted Techniques

6.4.3 Comparison to Other Methods

6.5 SA in Graph Search

6.5.1 Graph Search

6.5.2 AND/OR Graph Search

6.6 Statistical Inference and Hierarchical Structure

Chapter 7 the Expansion of Quotient Space Theory

7.1 Quotient Space Theory in System Analysis

7.1.1 Problems

7.1.2 Quotient Space Approximation Models

7.2 Quotient Space Approximation and Second Generation Wavelets

7.2.1 Second-Generation Wavelets Analysis

7.2.2 Quotient Space Approximation

7.2.3 The Relation between Quotient Space Approximation and Wavelet Analysis

7.2.4 Conclusions

7.3 Fractal Geometry and Quotient Space Analysis

7.3.1 Introduction

7.3.2 Iterated Function Systems

7.3.3 Quotient Fractals

7.3.4 Conclusions

7.4 The Extension of Quotient Space Theory

7.4.1 Introduction

7.4.2 Closure Operation based Quotient Space Theory

7.4.3 Non-partition Model based Quotient Space Theory

7.4.4 Granular Computing and Quotient Space Theory

7.4.5 Protein Structure Prediction-An Application of Tolerant Relation Based Theory

7.4.6 Conclusion

7.5 Conclusions

Addenda A: Some Concepts and Properties of Point Set Topology

A.1 Relation and Mapping

A.1.1 Relation

A.1.2 Equivalence Relation

A.1.3 Mapping and One-One Mapping

A.1.4 Finite Set, Countable Set and Uncountable Set

A.2 Topology Space

A.2.1 Metric Space

A.2.2 Topological Space

A.2.3 Induced Set, Close Set and Open Set

A.2.4 Interior and Boundary

A.2.5 Topological Base and Subbase

A.2.6 Continuous Mapping and Homeomorphism

A.2.7 Product Space and Quotient Space

A.3 Separability Axiom

A.3.1 T_{0} , T_{1} , T_{2} Spaces

A.3.2 T_{3} , T_{4} , Normalization and Normal Space

A.4 Countability Axiom

A.4.1 the First and Second Countability Axioms

A.4.2 Separable Space

A.4.3 Lindelof Space

A.5 Compactness

A.5.1 Compact Space

A.5.2 Relation between Compactness and Separability Axiom

A.5.3 Some Relations in Compactness

A.5.4 Local Compact and Paracompact

A.6 Connectedness

A.6.1 Connected Space

A.6.2 Connected Component and Local Connectedness

A.6.3 Arcwise Connected Space

A.7 Order-relation, Galois Connected and Closure Space

A.7.1 Order-relation and Galois Connected

A.7.2 Closure Operation and Closure Space

A.7.3 Closure Operations defined by Different Axioms

Addenda B: Some Concepts and Properties of Integral and Statistical Inference

B.1 Some Properties of Integral

B.1.1 Functions of Bounded Variation

B.1.2 LS Integral

B.1.3 Limit under Integral Symbol

B.2 Central Limit Theorem

B.3 Statistical Inference

B.3.1 SPRT Method

B.3.2 ASM Method