Constraint solving over multi-valued logics : application to digital circuits / Francisco Azevedo.

Format:

Book

Thesis/Dissertation

Author/Creator:

Azevedo, Francisco.

Series:

Frontiers in artificial intelligence and applications ; v. 91.

Frontiers in artificial intelligence and applications. Dissertations in artificial intelligence.

Frontiers in artificial intelligence and applications, 0922-6389 ; v. 91. Dissertations in artificial intelligence

Language:

English

Subjects (All):

Integrated circuits--Mathematical models.

Integrated circuits.

Digital electronics.

Physical Description:

1 online resource (223 p.)

Edition:

1st ed.

Place of Publication:

Amsterdam ; Oxford : IOS Press, c2003.

Language Note:

English

Summary:

Systems are subject to faults in their components, affecting their overall behaviour. This work addresses such problems developing models with multi-valued logics that it formalizes and generalizes to multiple faults. Such logics extend Boolean logic by encoding dependencies on faults.

Contents:

Cover

Title page

Table of Contents

Chapter 1. Introduction

1.1 Scope

1.2 Truth Maintenance Systems

1.3 Constraint Reasoning

1.3.1 Consistency Techniques

1.3.2 Maintaining Consistency

1.3.3 Advanced Techniques

1.4 Contributions and Limitations

1.4.1 Limitations

1.5 Overview

Chapter 2. Circuit Modelling

2.1 Introduction

2.2 Logic Simulation

2.3 Fault Modelling

2.4 Benchmarks

2.5 Our Modelling Approach

2.6 Summary

Chapter 3. Test Patterns

3.1 What are Test Patterns?

3.2 Test Generation

3.3 TG Modelling Approaches and Algorithms

3.3.1 Algebraic Models / Algorithms

3.3.2 Topological Methods

3.3.3 Multi-valued Logics

3.3.4 TG Specialised Algorithms

3.4 Constraint Reasoning

3.4.1 CLP(B)

3.4.2 CLP(FD)

3.5 Heuristics

3.5.1 Discussion and Potential Improvements

3.6 Iterative Time-Bounded Search

3.6.1 Conclusion

3.7 Summary

Chapter 4. Differential Diagnosis

4.1 Introduction

4.2 Diagnosis Approaches

4.3 Differential Diagnosis and Test Patterns

4.4 The 8-valued Logic

4.4.1 Boolean operations

4.4.2 Modelling Alternative Diagnostic Theories in Digital Circuits

4.5 A 4-valued Logic for Differentiation

4.6 A Constraint Solver for the 8-Valued Logic

4.6.1 Domain Representation

4.6.2 Not-Gates

4.6.3 Xor-Gates

4.6.4 Normal And-Gates

4.6.5 S-Buffers

4.6.6 Heuristics to Find Differential Patterns_

4.7 Benchmarks

4.7.1 Generating a Benchmark

4.7.2 Set of Benchmarks Used

4.8 Differentiating Multiple Diagnoses

4.9 Experimental Results

4.9.1 Choosing the Heuristic

4.9.2 Discussion

4.9.3 Complete Results

4.9.4 Comparison of Results and Approaches

4.10 Conclusions

Chapter 5. Problems with Multiple Diagnoses

5.1 Satisfaction Problems

5.1.1 Fault Simulation

5.1.2 Test Generation.

5.1.3 Fault Covering

5.1.4 Covered Diagnoses

5.1.5 Diagnosis

5.1.6 Fault Location

5.2 Optimisation Problems

5.2.1 Minimal Set of Test Patterns

5.2.2 Maximal Test Patterns

5.2.3 Minimal Diagnosis

5.2.4 Maximal Fault Resolution

5.3 Logic over Booleans and Sets

5.3.1 Signal Representation

5.3.2 Normal Gates

5.3.3 S-Buffers

5.4 Modelling and Solving

5.4.1 Diagnosis

5.4.2 Differentiation

5.4.3 Optimisation Problems

5.5 Reduction to Set Algebra

5.5.1 Motivation

5.5.2 Transformation

5.5.3 Modelling

5.6 Summary

Chapter 6. A New Set Constraint Solver: Cardinal

6.1 Set Constraint Solving and Cardinality Inferences

6.2 Intervals and Lattices

6.3 Operational Semantics

6.3.1 Set Variable

6.3.2 Membership Constraints

6.3.3 Set Complement

6.3.4 Set Equality

6.3.5 Set Inequality

6.3.6 Disjointness

6.3.7 Set Inclusion

6.3.8 Set Intersection

6.3.9 Set Union

6.3.10 Set Difference

6.4 Implementation

6.4.1 Set Labelling

6.5 Results

6.6 Other Applications

6.6.1 Steiner Triples

6.6.2 Golfers

6.6.3 Warehouse

6.6.4 Differential Diagnosis

6.7 Cardinal Extensions

6.7.1 Sets Union

6.7.2 Generalisation to Sets Functions

6.7.3 Set Covering

6.7.4 Results

6.7.5 Future Research

6.8 Conclusions

Chapter 7. Test Pattern Optimisation

7.1 Description

7.2 SAT Approach

7.3 5-valued Logic

7.4 Completeness

7.5 Naming Unspecified Values for an Extended Logic

7.5.1 Fault Detection Conditions

7.6 Local Search

7.6.1 A Multiple Extended Logic for Local Search

7.6.2 Operational Semantics

7.6.3 Improving Local Search

7.6.4 Multiple unspecification

7.7 Solution Spaces

7.8 Combining Logics

7.9 Results

7.10 Conclusions

Chapter 8. Generalisation, Discussion and Conclusion

8.1 Generalisation.

8.2 Conclusion and Research Directions

References

Appendix A: ISCAS Circuits

Appendix B: Logics.

Notes:

Bibliographic Level Mode of Issuance: Monograph

Thesis (Ph. D.)--UNL/FCT.

Includes bibliographical references and index.

ISBN:

1-280-50577-X

1-60129-412-3

600-00-0377-3

9786610505777

OCLC:

53011694