06325nam 2200673Ia 450 991081792240332120240410110851.01-280-50577-X1-60129-412-3600-00-0377-39786610505777(CKB)111082128295642(OCoLC)53011694(CaPaEBR)ebrary10116478(SSID)ssj0000129244(PQKBManifestationID)11139856(PQKBTitleCode)TC0000129244(PQKBWorkID)10069695(PQKB)10527541(MiAaPQ)EBC267482(Au-PeEL)EBL267482(CaPaEBR)ebr10116478(CaONFJC)MIL50577(OCoLC)814456826(EXLCZ)9911108212829564220021001d2003 uy 0engurcn|||||||||txtccrConstraint solving over multi-valued logics[electronic resource] application to digital circuits /Francisco Azevedo1st ed.Amsterdam ;Oxford IOS Pressc20031 online resource (223 p.)Frontiers in artificial intelligence and applications,0922-6389 ;v. 91.Dissertations in artificial intelligenceBibliographic Level Mode of Issuance: Monograph1-58603-304-2 0-585-45860-X Includes bibliographical references and index.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.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.Frontiers in artificial intelligence and applications ;v. 91.Frontiers in artificial intelligence and applications.Dissertations in artificial intelligence.Integrated circuitsMathematical modelsDigital electronicsIntegrated circuitsMathematical models.Digital electronics.621.395Azevedo Francisco1626395MiAaPQMiAaPQMiAaPQBOOK9910817922403321Constraint solving over multi-valued logics3962393UNINA