Problem-Solving Methods

State Machines [Gurevich, 1994]. Basically, MLPM and MCL extend MLCM with new elementary state transition types which cover the grainsize of state transitions in knowledge-based reasoning. As a consequence, we get an approach that integrates existing proposals, overcomes several of their shortcomings and ad-hoc solutions, and provides an axiomatization which enables the use of mechanized proof support. The structure of this chapter is as follows. First, we introduce the knowledge specification languages (ML) 2 and KARL focusing on their dynamics. We use the experience with these languages to derive requirements for an appropriate semantic framework for the specification of the dynamics of the reasoning of knowledge-based systems. Then we introduce the logics MLPM and MCL and provide their syntax and semantics. We use MCL to formalize the inference and control constructs of the KADS languages and Abstract State Machines and provide a comparison with work that uses different solutions. 4.1 Specification Languages for Knowledge-Based Systems In this subsection we introduce the two languages KARL and (ML) 2 , focusing on their formal means for specifying the reasoning process of knowledge-based systems. Both use variants of the CommonKADS model of expertise as conceptual framework (i.e., system architecture) for specifying a knowledge-based system. CommonKADS [Schreiber et al., 1994] uses task and inference layers for specifying the reasoning process. The task layer introduces the goal that is to be achieved by the system and it decomposes the overall task into subtasks and defines control over them. It combines a functional specification with the specification of the dynamic reasoning process that realizes the functionality. The inference layer defines the elementary inference steps, the relations between them, and the role of the domain knowledge for the reasoning process. A simple example will be used to illustrate the modeling concepts of both languages (see Fig. 21). The task of the knowledge-based system consists of finding the diagnosis with the highest preference for a given set of symptoms. Our example consists of two inference actions: • generate , which creates possible hypotheses based on the given findings and the causal relationships at the domain layer, and • select , which assigns a preference to hypotheses and selects the diagnosis with the highest preference. The knowledge role finding provides input to the inference action generate , the knowledge role hypothesis delivers the results of the reasoning of generate to select , and the knowledge role diagnosis provides the results of select as output. The two knowledge roles causality and preference provide knowledge necessary for the inference process. It is mapped from the domain layer. A simple control flow at the task layer is defined by first executing generate and then applying select to its output. 1) COLD, Common Object-oriented Language for Design, was developed at Phillips Research Eindhoven in several ESPRIT-projects (cf. [Feijs & Jonkers, 1992]). 4 Logics for Knowledge-Based Systems: MLPM and MCL 63