Modal Change Logic (MCL): Specifying the reasoning of knowledge-based systems

We investigate the formal specification of the reasoning process of knowledge-based systems in this paper. We analyze the corresponding parts of the KADS specification languages KARL and (ML)² and deduce some general requirements. The essense of these languages is that they integrate a declarative specification of inferences with control information. The languages differ in the way they achieve this integration and each of them has shortcomings. We propose a unifying semantical framework that integrates the core of the different solutions and overcomes their problems. We define a semantics and axiomatization with the Modal Change Logic (MCL). The main contribution of the paper is not to introduce yet another specification language. Instead we aim at four goals: (1) defining a framework for describing the dynamic reasoning behavior of knowledge-based systems which integrates existing approaches; (2) defining a semantics for the specification of the dynamic reasoning behavior of a knowledge-based system within the states as algebras setting that overcomes several shortcomings and ad hoc solutions of existing approaches; and (3) providing an axiomatization that enables the development of mechanized proof support. (4) Through conceptual and semantical clarity, we investigate the relationships to similar work in software engineering and database engineering opening possibilities for further cross-fertilization of these fields.     

Task structures as a basis for modeling knowledge-based systems

Recently, there has been an increasing interest in improving the reliability and quality of AI systems. As a result, a number of approaches to knowledge-based systems modeling have been proposed. However, these approaches are limited in formally verifying the intended functionality and behavior of a knowledge-based system. In this article, we proposed a formal treatment to task structures to formally specify and verify knowledge-based systems modeled using these structures. The specification of a knowledge-based system modeled using task structures has two components: a model specification that describes static properties of the system, and a process specification that characterizes dynamic properties of the system. The static properties of a system are described by two models: a model about domain objects (domain model), and a model about the problem-solving states (state model). The dynamic properties of the system are characterized by (1) using the notion of state transition to explicitly describe what the functionality of a task is, and (2) specifying the sequence of tasks and interactions between tasks (i.e., behavior of a system) using task state expressions (TSE). The task structure extended with the proposed formalism not only provides a basis for detailed functional decomposition with procedure abstraction embedded in, but also facilitates the verification of the intended functionality and behavior of a knowledge-based system. © 1997 John Wiley & Sons, Inc.     

TOWARD A COMMON STRUCTURAL LEVEL FOR SOFTWARE,DATABASE, AND KNOWLEDGE-BASED SYSTEMS

Abstract

Different languages, tools, and techniques are used for the development of software systems, including database and knowledge-based systems. Although underlying languages employ structuring concepts such as classification, modularization, generalization, and perspectives, these common concepts remain overshadowed by differing terminologies and notations, due to the separate histories of software engineering, databases, and knowledge representation. Currently the still more complex and ambitious requirements on software systems call for integrated solutions concerning software engineering environments. As a starting point toward integration, in this paper we aim at deriving a common structural level for software systems. To approach this goal we start by analyzing the human thought process on one hand and successfully applied structuring techniques on the other hand to derive a catalogue of 10 structuring concepts. Building on that, a self-contained language called SFW (structuring framework) is introduced to provide means for a general and uniform specification of the structure of software systems. SFW is aimed at providing a catalogue of reference for structuring concepts in today's languages as well as a suggestion to establish a uniform structural level in future approaches.     

Defining the abstract syntax of visual languages with advanced graph grammars—A case study based on behavior trees

Diagrammatic visual languages can increase the ability of engineers to model and understand complex systems. However, to effectively use visual models, the syntax and semantics of these languages should be defined precisely. Since most diagrammatic visual models that are currently used to specify systems can be described as (directed) typed graphs, graph grammars have been identified as a suitable formalism to describe the abstract syntax of visual modeling languages. In this article, we investigate how advanced graph-transformation techniques, such as conditional, structure-generic and type-generic graph-transformation rules, can help to improve and simplify the specification of the abstract syntax of a visual modeling language. To demonstrate the practicability of an approach that unifies these advanced graph-transformation techniques, we define the abstract syntax of behavior trees (BTs), a graphical specification language for functional requirements. Additionally, we provide a translational semantics of BTs by formalizing a translation scheme to the input language of the SAL model checking tool for each of the graph-transformation rules.     

Modeling high assurance agent-based Earthquake Management System using formal techniques

Disaster management systems are complex applications due to their distributed and decentralized nature. Various components execute in parallel with high need of coordination with each other. In such applications, interaction and communication issues are difficult to model and implement. In this paper, we have proposed agent-based Earthquake Management System (EMS) which is modeled and analyzed using formal approach. Traditionally, such systems undergo through various transformations starting from requirement models and specification to analysis, design and implementation. A variety of formal approaches are available to specify systems for analyzing their structure and behavior; however, there are certain limitations in using these techniques due to their expressiveness and behavior requirements. We have adopted combination of Pi-calculus and Pi-ADL formal languages to model EMS from analysis to design. The formal approach helps to enhance reliability and flexibility of the system by reducing the redundant information. It reduces chances of errors by explicitly mentioning working flow of information. Additionally, a prototype application is presented as proof of concept in EMS context. We have also evaluated our formal specification by using ArchWare and ABC tools; also, comparison of prototype application with major existing techniques is highlighted.     

Specification of Real-Time Systems in UML

We introduce time semantics into UML class and statechart diagrams. This extends the expressiveness of UML for specification of real-time systems and allows to specify verification properties of real-time systems by means of Timed Computation Tree Logic. We furthermore propose a way to collect stereotypes for specification of real-time systems. The approach is illustrated by a case study.     

An Aspect-Oriented Approach to Modular Behavioral Specification

Behavioral interface specification languages, such as Java Modeling Language (JML), can be used to specify the behavior of program modules. We have developed a behavioral interface specification language Moxa, an extension of JML. Moxa provides a new modularization mechanism called assertion aspect that can capture the crosscutting properties among assertions. In this paper, we briefly explain the notion of assertion aspects and the design of Moxa, and then we show an example specification. By comparing the specification to its JML counterpart, we show that the use of assertion aspects clarifies the large, complex specification and greatly simplifies each assertion in the specification.     

An organizational approach to designing an intelligent knowledge-based system: Application to the decision-making process in design projects

Knowledge-based engineering (KBE) approaches are designed to reduce the time and cost of product development by capturing, retaining and re-using design knowledge. They currently focus on repetitive design tasks where knowledge is considered as a static resource. However, knowledge is intrinsically linked to the organizations and people who use it. Thus, to be efficient, these knowledge-based systems (KBS) have to be able to take into account all the mechanisms of knowledge creation, sharing and evaluation made by the users. Using the agent paradigm, new knowledge-based systems can be designed in order to address this research issue. Indeed, the agents have social abilities and are able to achieve very complex tasks. These two features are necessary for making a knowledge-based system efficient. However, there still exists today a lack of approaches and methodologies to help design such applications. This paper presents DOCK, a methodology to design an intelligent knowledge-based system that aims to support the knowledge management process. In order to take into account all the mechanisms of knowledge generation, sharing and re-use, DOCK is based on the hypothesis that efficient modelling of human organizations, by highlighting their roles, collaborations, skills, goals and knowledge, will help the KBS designer to specify an adapted knowledge-based system. Finally, DOCK is implemented to design the SMA SNOTRA that is dedicated to supporting a decision-making process for design projects.     

Formal specification of design pattern combination using BPSL

Pattern users are faced with difficulties in understanding when and how to use the increasing number of available design patterns due the inherent ambiguity in the existing means (textual and graphical) of describing them. Since patterns are seldom used in isolation but are usually combined to solve complex problems, the above-mentioned difficulties have even worsen.Hence, there is an appealing need to introduce formalism to accurately describe patterns and pattern combination to allow rigorous reasoning about them. The main problem of existing formal specification languages for design patterns is lack of completeness. This is mainly due either because they were not originally conceived to specify design patterns and have been adapted to do so, or they tend to focus on specifying either the structural or behavioral aspect of design patterns but not both of them. Moreover, only few of them venture in specifying design pattern combination.We propose a simple yet Balanced Pattern Specification Language that is aimed to achieve equilibrium by specifying the structural as well as behavioral aspects of design patterns. This is achieved by combining two subsets of logic one from First Order Logic and one from Temporal Logic of Actions. Moreover it can be used to formally specify pattern combination.     

Verification of Knowledge-Based Systems Using Predicate/Transition Nets

As expert-system technology gains broader acceptance, the need to build and maintain large-scale knowledge-based systems (KBSs) will assume greater importance. Traditional approaches to KBS verification generally contain no predicate/transition (PrT) net models, thus making them slow for the large-scale KBS with chained errors. This paper proposes an attractive alternative to KBS verification, in which the KBS is modeled as a PrT-net model. Then, the least fixpoint semantics of the PrT-net model can be introduced into the KBS for the purpose of speeding up the computations of the KBSs. The significance of this paper is that seven propositions are formulated to detect errors of redundancy, subsumption, unnecessary condition, circularity, inconsistency, dead end, and unreachable goal. Thus, the performance of a computer-aided-design tool for KBSs can be improved to some extent. Meanwhile, specification languages, including Programming in Logic, Frame-and-Rule-Oriented Requirements Specification Language, and the like, are suitable to this approach.     

Rule-based systems formalized within a software architectural style

This article considers the utilization of architectural styles in the formal design of knowledge-based systems. The formal model of a style is an approach to systems modeling that allows software developers to understand and prove properties about the system design in terms of its components, connectors, configurations, and constraints. This allows commonality of design to be easily understood and captured, leading to a better understanding of the role that an architectural abstraction would have in another complex system, embedded context, or system integration. In this article, a formal rule-based architectural style is presented in detail using the Z notation. The benefits of depicting the rule-based system as an architectural style include reusability, understandability, and the allowance for formal software analysis and integration techniques. The ability to define the rule-based architectural style in this way, illustrates the power, clarity, and flexibility of this specification form over traditional formal specification approaches. In addition, it extends current verification approaches for knowledge-based systems beyond the knowledge base only.     

Development of global specification for dynamically adaptive software

As software systems are becoming increasingly complex, they need to dynamically and continually adapt their behavior to changing conditions in the long-term running. There will be large numbers of adaptations in these systems when evolving and the adaptations may be unknowable until system operation. To specify these adaptations, this paper proposes the mode-supported Linear Temporal Logic (mLTL) that is an effective way to describe global specifications of adaptive software. The global specifications are defined for adaptive software as requirements from the perspective of global adapting process. The model checking problem of mLTL is also resolved using Linear Temporal Logic (LTL) and Labelled Transition System Analyser (LTSA). Finally, we provide a prototype implementation for modelling and analyzing adaptive programs, and experimental evaluation shows feasibility and scalability of our approach.     

An event-based approach for formally verifying runtime adaptive real-time systems

Real-time and embedded systems are required to adapt their behavior and structure to runtime unpredicted changes in order to maintain their feasibility and usefulness. These systems are generally more difficult to specify and verify owning to their execution complexity. Hence, ensuring the high-level design and the early verification of system adaptation at runtime is very crucial. However, existing runtime model-based approaches for adaptive real-time and embedded systems suffer from shortcoming linked to efficiently and correctly managing the adaptive system behavior, especially that a formal verification is not allowed by modeling languages such as UML and MARTE profile. Moreover, reasoning about the correctness and the precision of high-level models is a complex task without the appropriate tool support. In this work, we propose an MDE-based framework for the specification and the verification of runtime adaptive real-time and embedded systems. Our approach stands for Event-B method to formally verify resources behavior and real-time constraints. In fact, thanks to MDE M2T transformations, our proposal translates runtime models into Event-B specifications to ensure the correctness of runtime adaptive system properties, temporal constrains and nonfunctional properties using Rodin platform. A flood prediction system case study is adopted for the validation of our proposal.

     

Dynamic Meta Modeling with Time: Specifying the Semantics of Multimedia Sequence Diagrams

UML offers different diagram types to model behavior and dynamics of software systems. In some domains like embedded real-time systems or multimedia systems, it is necessary to include specifications of time since the correctness of these applications depends on the fulfillment of temporal requirements in addition to functional requirements. UML thus already incorporates language features to model time and temporal constraints. Such model elements must have an equivalent in the semantic domain. We have proposed Dynamic Meta Modeling (DMM) as a means for the specification of the formal operational semantics of UML models by applying graph transformation to the meta modeling of dynamic behavior. Within this paper, we extend this approach to also account for time by building on timed graph transformations. We apply these concepts to the domain of multimedia application modeling in which we adopt UML sequence diagrams. The DMM rules with time then specify an interpreter that can be used to analyze or test a model of multimedia sequence diagrams.     

Testing timed systems modeled by Stream X-machines

Stream X-machines have been used to specify real systems where complex data structures. They are a variety of extended finite state machine where a shared memory is used to represent communications between the components of systems. In this paper we introduce an extension of the Stream X-machines formalism in order to specify systems that present temporal requirements. We add time in two different ways. First, we consider that (output) actions take time to be performed. Second, our formalism allows to specify timeouts. Timeouts represent the time a system can wait for the environment to react without changing its internal state. Since timeous affect the set of available actions of the system, a relation focusing on the functional behavior of systems, that is, the actions that they can perform, must explicitly take into account the possible timeouts. In this paper we also propose a formal testing methodology allowing to systematically test a system with respect to a specification. Finally, we introduce a test derivation algorithm. Given a specification, the derived test suite is sound and complete, that is, a system under test successfully passes the test suite if and only if this system conforms to the specification.     

Mapping visual to textual knowledge representation

In this paper, graphical representations for knowledge structures in the design method DESIRE for component-based design of knowledge and multi-agent systems are presented, together with a graphical editor based on the Constraint Graph environment. Moreover, a translator is described which translates these graphical representations to textual representations in DESIRE. The strength of the combined environment is a powerful—yet easy-to-use—framework to support the development of knowledge-based and multi-agent systems. Finally, a mapping is presented from DESIRE to Conceptual Graphs. This provides a unifying perspective on the knowledge representation format of DESIRE and allows the use of conceptual graph tools to specify and maintain the knowledge representation part of a DESIRE specification.     

The Control Layer in Open Mechanized Reasoning Systems: Annotations and Tactics

We are interested in developing a methodology for integrating mechanized reasoning systems such as Theorem Provers, Computer Algebra Systems, and Model Checkers. Our approach is to provide a framework for specifying mechanized reasoning systems and to use specifications as a starting point for integration. We build on the work presented by Giunchigliaet al. (1994) which introduces the notion of Open Mechanized Reasoning Systems (OMRS) as a specification framework for integrating reasoning systems. An OMRS specification consists of three components: the logic component, the control component, and the interaction component. In this paper we focus on the control level. We propose to specify the control component by first adding control knowledge to the data structures representing the logic by means of annotations and then by specifying proof strategies via tactics. To show the adequacy of the approach we present and discuss a structured specification of constraint contextual rewriting as a set of cooperating specialized reasoning modules.