I am indebted to my thesis advisor, Michael Genesereth, for his guidance, inspiration, and support which has made this research possible. As a teacher and a sounding board for new ideas, Mike was extremely helpful in pointing out Haws, and suggesting new directions to explore. I would also like to thank Harold Brown for introducing me to the application of artificial intelligence to reasoning about designs, and his many valuable comments as a reader of this thesis. Significant contribu­ tions by the other members of my reading committee, Mark Horowitz, and Allen Peterson have greatly improved the content and organization of this thesis by forcing me to communicate my ideas more clearly. I am extremely grateful to the other members of the Logic Group at the Heuristic Programming Project for being a sounding board for my ideas, and providing useful comments. In particular, I would like to thank Matt Ginsberg, Vineet Singh, Devika Subramanian, Richard Trietel, Dave Smith, Jock Mackinlay, and Glenn Kramer for their pointed criticisms. This research was supported by Schlumberger Palo Alto Research (previously Fairchild Laboratory for Artificial Intelligence). I am grateful to Peter Hart, the former head of the AI lab, and his successor Marty Tenenbaum for providing an excellent environment for performing this research.

Inhalt

1 Introduction.- 1.1 Motivation.- 1.2 Exploiting Design Morphology.- 1.3 Methodology.- 1.4 Example.- 1.5 Relationship to other work.- 1.5.1 Reasoning about devices.- 1.5.2 Reformulating representations.- 1.6 Overview.- 2 Reformulation.- 2.1 Devices and Designs.- 2.1.1 Definition of a Device.- 2.1.2 Definition of a Design.- 2.2 Reformulating Designs.- 2.2.1 Abstracting Designs.- 2.2.2 Repartitioning Designs.- 2.2.3 Making Design Knowledge Explicit/Implicit.- 2.3 Design Correctness.- 2.3.1 Correctness for an Abstraction Level.- 2.3.2 Correctness Between Adjacent Abstraction Levels.- 2.4 Automatically Reformulating Designs.- 2.5 Manually Reformulating Designs.- 3 General Representation and Reasoning.- 3.1 Requirements for a Design Description Language.- 3.2 Syntax and Semantics for Predicate Calculus.- 3.3 Describing Designs.- 3.4 Automated Deduction.- 3.4.1 Simulation.- 3.4.2 Diagnosis.- 3.4.3 Test Generation.- 3.4.4 Control.- 3.5 Utility of General Representation and Reasoning.- 3.5.1 Advantages.- 3.5.2 Disadvantages.- 4 Test Generation.- 4.1 Task Definition.- 4.2 Previous Work.- 4.3 The Saturn Test Generation System.- 4.3.1 Algorithm.- 4.3.2 Example.- 4.3.3 Control Strategies to Increase Efficiency.- 4.3.4 Empirical Evaluation.- 5 Conclusion.- 5.1 Summary of Key Ideas.- 5.2 Further Work.- 5.3 Implementation State.- A Printer Adapter Card.- B Tests for the Printer Adapter Card.