Specifying transaction-based information systems with regularexpressions

The work is about the formal specification of transaction-based, interactive information systems. A transaction is a task that the user can execute independently, and the system can be defined as a partially ordered set of transactions. The general framework is the transformational paradigm, based on the classical Waterfall development model (W.W. Royce, 1970). The stages are systems analysis, software specification, design, and implementation. The systems analysis and software specification stages are covered. An informal, transaction-oriented method for systems analysis is proposed. The resulting system specification involves two parts: a high-level specification of each transaction and a formal specification of the system's control flow, i.e., the order of execution of the transactions. The system's control flow is expressed in a formal language describing concurrent regular expressions built on transaction names. At the software specification stage, some operational requirements, such as connect/disconnect transactions and the application of the all-or-nothing principle, are added to the system specification. Then a serial product automaton (SPA) is used to transform the concurrent expression into a single regular expression. This result is proven to be consistent with the system specification     

基于图文法的并发系统状态测试方法及其实现

在并发系统的研究和开发中，迫切需要一种能正确有效地描述并发系统的动态进程互联结构、动态进程通信和进程演化行为的形式化方法以及基于这种形式化方法的并发系统动态状态的测试手段．本文介绍一种基于图文法模型的并发系统状态测试方法，该方法与描述并发系统结构和行为的图文法模型相结合，构成了一个并发系统开发支持环境．这一方法可根据对并发系统的状态测试要求，在并发系统的运行期自动跟踪和记录并发系统的运行状态和通信情况，使并发系统的开发者可以实时地得到并发系统的运行状态，或者在并发系统运行结束后重演并发系统的状态变化过程.     

Specifying an expert system

The success of numerous expert systems in practical applications warrants a more formal approach to their development and evaluation. Reliability assurance of expert systems requires a methodology for the specification and evaluation of these systems. Expert systems are a new class of software system, but some traditional techniques of software development may be adapted to their construction. However, the specification of an expert system differs from that of a more traditional software program in that parts of the specification are permitted to be only partially described when development starts.

Specifications have two important purposes: as contracts between suppliers and clients, and as blueprints for implementation. A specification consists of a problem specification and a solution specification. The problem specification plays the role of contract and states explicitly what the problem to be solved is, and the constraints that the final product must satisfy. The solution specification plays the role of blueprint and has two major aspects: analyzing how a human expert solves the problem, and proposing an equivalent automated solution. We propose an approach to the specification of expert systems that is flexible, yet rigorous enough to cover the important features of a wide range of potential expert system applications. We describe fully each of the components of an expert system specification and we relate specification to the issues of evaluation and maintenance of expert systems.     

Synthesizing structured analysis and object‐based formal specifications

Structured Analysis (SA) is a widely‐used software development method. SA specifications are based on Data Flow Diagrams (DFD's), Data Dictionaries (DD's) and Process Specifications (P‐Specs). As used in practice, SA specifications are not formal. Seemingly orthogonal approaches to specifications are those using formal, object‐based, abstract model specification languages, e.g., VDM, Z, Larch/C++ and SPECS. These languages support object‐based software development in that they are designed to specify abstract data types (ADT's). We suggest formalizing SA specifications by: (i) formally specifying flow value types as ADT's in DD's, (ii) formally specifying P‐Specs using both the assertional style of the aforementioned specification languages and ADT operations defined in DD's, and (iii) adopting a formal semantics for DFD “execution steps”. The resulting formalized SA specifications, DFD‐SPECS, are well‐suited to the specification of distributed or concurrent systems. We provide an example DFD‐SPEC for a client‐server system with a replicated server. When synthesized with our recent results in the direct execution of formal, model‐based specifications, DFD‐SPECS will also support the direct execution of specifications of concurrent or distributed systems.     

一种从Object—Z到CSP规格说明的转化方法

面向对象形式规格说明语言Object-Z与进程代数CSP相结合是当今的一个热点,它既可以表示复杂的模块化数据与算法,又可以表示系统的行为,但求精与验证对它们结合后的规格说明需要分别进行处理。本文提出了一个方法,把Object-Z规格说明转化为CSP规格说明,可以方便地处理结合后的规格说明,因此求精与推理对结合后的规格说明可以按CSP规则与方法一致来进行处理。此外,转化后的Object-Z规格说明可以按照CSP方法进行模型检查。     

A methodology for constructing of philosophy ontology based on philosophical texts

An ontology is a crucial factor for the success of the Semantic Web and other knowledge-based systems in terms of share and reuse of domain knowledge. However, there are a few concrete ontologies within actual knowledge domains including learning domains. In this paper, we develop an ontology which is an explicit formal specification of concepts and semantic relations among them in philosophy. We call it a philosophy ontology. Our philosophy is a formal specification of philosophical knowledge including knowledge of contents of classical texts of philosophy. We propose a methodology, which consists of detailed guidelines and templates, for constructing text-based ontology. Our methodology consists of 3 major steps and 14 minor steps. To implement the philosophy ontology, we develop an ontology management system based on Topic Maps. Our system includes a semi-automatic translator for creating Topic Map documents from the output of conceptualization steps and other tools to construct, store, retrieve ontologies based on Topic Maps. Our methodology and tools can be applied to other learning domain ontologies, such as history, literature, arts, and music.     

UML specification of access control policies and their formal verification

Security requirements have become an integral part of most modern software systems. In order to produce secure systems, it is necessary to provide software engineers with the appropriate systematic support. We propose a methodology to integrate the specification of access control policies into Unified Modeling Language (UML) and provide a graph-based formal semantics for the UML access control specification which permits to reason about the coherence of the access control specification. The main concepts in the UML access control specification are illustrated with an example access control model for distributed object systems.     

Formal interaction specification in public health surveillance systems using pi-calculus

This paper provides formal specification of interactions in typical public health surveillance systems involving healthcare agencies at local, state and federal levels. Although few standards exist for exchange of healthcare information, there is a general lack of formal models of the protocols involved in the interactions between the agencies. The quality of medical care provided is an end result of a well designed choreography of diverse services provided by different healthcare entities. One of the major challenges in this field appears to be explicit formal specification of such interactions. Such formal specification work is the first step leading to both design and verification of important properties of public healthcare systems. pi-calculus is a formal modeling technique for precise specification of semantics in interacting concurrent systems where mobility is involved. Two different configurations of public health surveillance systems are modelled using pi-calculus in this paper.     

A formal methodology using attributed grammars for multiprocessing-system software development. I. Design representation

With the growing complexity of multiprocessing systems and distributed computing systems, there is an increasing need to provide a formal methodology for deriving a model to represent software design for the software development of these systems. The formal methodology presented in this paper uses attributed grammars, and extends formal methods commonly used in the definition of programming languages and compiler techniques for representing the design specification of software systems and validating the implementation. This model provides a common basis in the software development phases through automated design analysis, test-case generation, and validation of the software system. This paper covers the construction of the model for the design representation using attributed grammar and the analysis of the software system design based on the model.     

Design of Ada Systems Yielding Reusable Components: An Approach Using Structured Algebraic Specification

Our experience with design of Ada¹ software has indicated that a methodology, based on formal algebra, can be developed which integrates the design and management of reusable components with Ada systems design. The methodology requires the use of a specification language, also based on formal algebra, to extend Ada's expressive power for this purpose. We show that certain requirements for the use of Ada packages which cannot be expressed in Ada can be expressed in algebraic specification languages, and that such specifications can then be implemented in Ada.     

A complete axiomatic semantics of spawning

Summary In modern imperative languages there are two commonly occurring ways to activate concurrently running tasks,splitting (cobegin...coend) andspawning. The programming language Ada makes use of both forms of task activation. We present a formal system for verifying partial correctness specifications of Ada tasks activated by spawning. The system is based upon a view of tasks as histories of events. We show how the mindset of splitting may be applicable when developing a formal system for reasoning about spawning. The resultant proof system is compositional, and a robust extension of partial correctness proof systems for sequential constructs. A transition model is given for spawning, and the proof system is proven complete in the sense of Cook [10] relative to this model, under certain reasonable assumptions. The specific proof rules given apply to a subset of Ada without real-time and distributed termination. Our approach to task verification applies to other imperative languages besides Ada, and the essential parts of our methodology are applicable to other formal systems besides those based on partial correctness reasoning. Sigurd Meldal is professor of informatics at the University of Bergen. He is interested in techniques and tools based on formal methods for development of concurrent software. His current foci are the investigation of algebraic approaches to nondeterminism, and the participation in the design of a concurrent specification, prototyping and implementation language. The latter supplements formal proof with support for run time control of consistency between concurrent systems as specified and as implemented. Meldal received his cand. real. (1982) and dr. scient. (1986) degrees in informatics from the University of Oslo.This research was supported by a grant from the Norwegian Research Council for Science and the Humanities, by the Defense Advanced Research Projects Agency/Information Systems Technology Office under the office of Naval Research contract N00014-90-J1232, by the Air Force Office of Scientific Research under Grant AFOSR83-0255 and by a Fulbright Scholarship from the US Educational Foundation in Norway     

A generalization of the E-LOTOS renaming operator: a convenience for specification of new forms of process composition

E-LOTOS is one of the standard languages for formal specification of real-time concurrent and reactive systems. As it is process-algebraic, its expressive power lies in its process-composition operators. Of course, not all forms of composition can be directly expressed in the language. In the most difficult cases, one typically resorts to the constraint-oriented specification style. We demonstrate that a slight enhancement of the E-LOTOS renaming operator would make the specification style even more powerful. As an example, we show how to specify choice, parallel composition and disabling enhanced with action priorities.     

The Input Model of Standard Graphics Systems Revisited by Formal Specification

This paper describes the specification of an input model for graphics systems. The initial aim of the work reported in this paper was to revise the input model adopted by graphics standards by means of formal specification techniques in order to acquire a deep knowledge of its capabilities, to eventually discover errors and to develop improvements. Taking into account similar works done in this area by others and considering a number of major issues related to input recently discussed within the graphics community, a new model is being proposed that addresses the very key concepts of parallelism, extensibility and reconfigurability. The model is based upon composition operations defined over basic components specified as a set of concurrent processes. Composition operations and process definitions have been formally specified by using the LOTOS notation and investigated by means of the LOTOS Interactive Tools Environment. In the first part of the paper, the input model of graphics standards is shortly examined in the light of the results so far achieved by related works on formal specification of computer graphics systems. Subsequently, an improved model is presented. Finally, its capability of simulating the traditional operating modes of logical input devices and a methodology for defining new operating modes is demonstrated.     

Heuristic search for equivalence checking

Equivalence checking plays a crucial role in formal verification since it is a natural relation for expressing the matching of a system implementation against its specification. In this paper, we present an efficient procedure, based on heuristic search, for checking well-known bisimulation equivalences for concurrent systems specified through process algebras. The method tries to improve, with respect to other solutions, both the memory occupation and the time required for proving the equivalence of systems. A prototype has been developed to evaluate the approach on several examples of concurrent system specifications.     

Towards a Formal Treatment of Implicit Invocation Using Rely/Guarantee Reasoning

Implicit invocation [SuN92, GaN91] has become an important architectural style for large-scale system design and evolution. This paper addresses the lack of specification and verification formalisms for such systems. A formal computational model for implicit invocation is presented. We develop a verification framework for implicit invocation that is based on Jones' rely/guarantee reasoning for concurrent systems [Jon83, St?91]. The application of the framework is illustrated with several examples. The merits and limitations of the rely/guarantee paradigm in the context of implicit invocation systems are also discussed. Received August 1997 / Accepted in revised form June 1998     

The Evolution of Concurrent Programs

Process algebra are formal languages used for the rigorous specification and analysis of concurrent systems. By using a process algebra as the target language of a genetic programming system, the derivation of concurrent programs satisfying given problem specifications is possible. A genetic programming system based on Koza's model has been implemented. The target language used is Milner's CCS process algebra, and is chosen for its conciseness and simplicity. The genetic programming environment needs a few adaptations to the computational characteristics of concurrent programs. In particular, means for efficiently controlling the exponentially large computation spaces that are common with process algebra must be addressed. Experimental runs of the system successfully evolved a number of non–iterative CCS systems, hence proving the potential of evolutionary approaches to concurrent system development.