International Journal of Software Engineering and Knowledge Engineering

This article is on a methodology for eliciting and verifying the correctness of domain knowledge using propositional logic. The domain knowledge is further structured and organized into subdomains of objects to facilitate an automatic and rapid development of design prototypes. The philosophy of the design paradigm is threefold: 1) focus the development of software requirements specifications on a set of objects and a set of relationships; 2) establish theorems about the interrelationships of the objects, prove the correctness of the theorems, construct software architectural models based on the transitivity of the theorems, and decompose the models into clusters of objects; and 3) employ object-oriented design techniques to generate prototypes of object classes from the resultant clusters. A prototype generator has been implemented to realize these goals. The significant contributions of this paper are: 1) limiting the contents of the specifications to objects and relationships and mapping this dual basis approach into formalisms of logic to derive and verify the abstract interdependencies of the objects; and 2) modeling, decomposing, and clustering the objects into common classes to facilitate a modular design.

As part of the NASA/Goddard Code 522.3 research program in software engineering, a Knowledge-Based Software Engineering Environment (KBSEE) is being developed. The KBSEE will support a comprehensive artifact-reuse capability and will incorporate knowledge-based concepts such as machine learning and design knowledge capture. The distinguishing features of this work are that it is a systematic approach to the reuse of knowledge, not just of products, and it implements learning as an explicitly supported function in a software engineering environment.

Each of these objectives is currently being pursued in a distinct prototype environment: design knowledge capture and knowledge reuse in KAPTUR (Knowledge Acquisition for Preservation of Tradeoffs and Underlying Rationales), and learning in LEARN (Learning Enhanced Automation of Reuse Engineering). Despite their prototype realization in different environments, the integration of these approaches into an overall KBSEE is a key goal of our work.

Conjunctive match is often used in Artificial Intelligence as the kernel of a pattern-directed inference [37] engine. Conjunctive match entails generating and testing all possible combinations of objects against a pattern of constraints. While simple to program, it is an expensive, exponential cost computation.

To reduce this average match cost in production system engines, the RETE match algorithm [8] was devised. RETE compiles each rule's pattern of constraints into a network, and then incrementally updates partial matches as objects are inserted and deleted. RETE, however, has its own cost: conceptual and implementational complexity.

Call-graph caching (CGC) [20] is a mechanism for transforming recursive specifications into highly optimized networks. In this paper, we describe CGC, and use it to transform a family of recursive conjunctive match formulations into their corresponding RETE networks. Our approach illustrates the ideas behind RETE, and shows their application to other algorithms.

The paper discusses a problem associated with learning from examples. Learning programs under consideration, LEM and LERS, were designed to automate knowledge acquisition for expert systems. Hence, both programs induce rules in the minimal discriminant form, i.e., rules based on minimal sets of relevant attributes, called coverings.

The problem addressed in the paper is the selection of the best algorithm for determining coverings. Four different methods, based on indiscernibility relation, partition, characteristic set and lower boundary are compared. Both theoretical analysis and experimental results of multiple running of many sets of examples, with variable number of examples and with variable number of attributes are taken into account. As a result the partition method is determined to be the most efficient way to compute coverings.

This paper introduces an algorithm, LEM3, for incremental learning of production rules from examples. Based on the concept of rough sets introduced by Pawlak, LEM3 is capable of learning rules from consistent as well as inconsistent examples. In LEM3, rules are generated by using the rule-generating procedure implemented in a nonincremental learning program LEM2. Consequently, the rules learned by LEM3 do not use redundant attribute-value pairs.

One major feature of LEM3 is the incorporation of a separate global data structure for storing information learned from new examples. The global data structure is updated on an example by example basis, and it provides all the essential information for the incremental updating of lower and upper approximations of a concept and the generating of rules. This separation of learned knowledge from rule-generating procedures provides a more modular design of learning systems.

This paper examines the utility of much of the software metrics research that has been carried out in software engineering to problems in artificial intelligence. The paper first reviews the work that has been carried out and then makes a number of suggestions about how it could be transferred to the artificial intelligence arena — applying it in particular to expert system development.