Unifying Concurrent and Relational Refinement

Refinement in a concurrent context, as typified by a process algebra, takes a number of different forms depending on what is considered observable, where observations record, for example, which events a system is prepared to accept or refuse. Examples of concurrent refinement relations include trace refinement, failures-divergences refinement and bisimulation.Refinement in a state-based language such as Z, on the other hand, is defined using a relational model in terms of input/output behaviour of abstract programs. These refinements are verified by using two simulation rules which help make the verification tractable.The purpose of this paper is to unify these two standpoints, and we do so by generalising the standard relational model to include additional observable aspects. The central result of the paper is then to develop simulation rules to verify relations such as failures-divergences refinement in a relational setting, and show how these might be applied in a specification language such as Z.     

一种从Z到精化演算的软件开发方法

一、引言形式化方法的研究和应用已有二十多年的历史,源于Dijkstra和Hoare的程序验证以及Scott、stratchey等人的程序语义研究,指为保证复杂系统的可靠性,以数学为基础对其进行精确描述和验证的语言、技术和工具。形式化方法的关键在于形式规约语言。通过语法和语义有严格数学定义的形式规约语言对系统及其各方面性能的描述,产生系统的形式规约,可以帮助开发者获得对所描述系统的深刻理解,并通     

Refinement algebra with dual operator

Algebras of imperative programming languages have been successful in reasoning about programs. In general an algebra of programs is an algebraic structure with programs as elements and with program compositions (sequential composition, choice, skip) as algebra operations. Various versions of these algebras were introduced to model partial correctness, total correctness, refinement, demonic choice, and other aspects. We introduce here an algebra which can be used to model total correctness, refinement, demonic and angelic choice. The basic model of our algebra are monotonic Boolean transformers (monotonic functions from a Boolean algebra to itself).     

The Least Conjunctive Refinement and Promotion in the Refinement Calculus

A syntactic calculation of Morgan's least conjunctive refinement operator for predicate transformers is developed. The operator is used to develop a general approach to lifting relational operators to predicate transformer operators. Predicate transformer versions of the relational conjunction and disjunction operators are considered in detail. The Z-based technique of program promotion is considered in a refinement calculus setting. A standard Z promotion example is recast in the refinement calculus. Received August 1997 / Accepted in revised form January 1999     

Using the Alloy Analyzer to Verify Data Refinement in Z

In the development of critical systems, standards dictate that it is necessary to first design, construct and formally analyse abstract models of the system. Developers must then verify that the final implementation is consistent with these more abstract specifications.Z is an example of a state-based specification language. It has been shown to be effective in a variety of cases—indeed it was developed as part of a joint collaboration between Oxford University's PRG and IBM Hursley for the specification of the CICS system. However, Z's main weakness is that it does not have the necessary tool support: whilst there are associated type checkers, there is no tool for automatically verifying refinement in Z.The contribution of this paper is to show how data refinement in Z can be automatically verified using the Alloy Analyzer. The soundness and joint completeness of the simulation rules for Z have already been established: here we translate them to Alloy. We then show how data types expressed in Z can also be translated to Alloy, before presenting the assertions necessary for the Alloy Analyzer to identify the retrieve relation and hence verify refinement. We present a simple example in which the Alloy Analyzer successfully identifies the retrieve relation between two data types thereby verifying simulation and hence refinement. We conclude the paper with a discussion of the suitability of the Alloy Analyzer for such a task.     

A Program Refinement Tool

The refinement calculus for the development of programs from specifications is well suited to mechanised support. We review the requirements for tool support of refinement as gleaned from our experience with existing refinement tools, and report on the design and implementation of a new tool to support refinement based on these requirements. The main features of the new tool are close integration of refinement and proof in a single tool (the same mechanism is used for both), good management of the refinement context, an extensible theory base that allows the tool to be adapted to new application domains, and a flexible user interface. Received June 1997 / Accepted in revised form June 1998     

Action Refinement for Real-Time Concurrent Processes with Urgency

Action refinement for real=time concurrent processes with urgent interactions is studied, where a partial-order setting, i.e., timed bundle event structures, is used as the system model and a real-time LOTOS-like process algebra is used as the specification language. It is shown that the proposed refinement approaches have the commonly expected properties:(1) the behaviour of the refined process can be inferred compositionally from the behaviour of the original process and from the behaviour of the processes substituted for actions; (2) the timed extensions of pomset (partially ordered multiset) trace equivalence and history preserving bisimulation equivalence are both congruences under the refinement; (3) the syntactic and semantic refinements coincide up to the aforementioned equivalence relations with respect to a cpo-based denotational semantics.     

Refinement Patterns for UML

This paper describes strategies or 'patterns' for the refinement of UML specifications into executable implementations, using a semantically precise subset, UML-RSDS, of UML.     

一种基于代数语义的软件体系结构求精方法

软件体系结构是引导需求到实现的桥梁,目前在软件体系结构建模方法中主要分为形式化和非形式化两种。针对大型分布式系统的体系结构采用Petri网进行建模,兼顾了可视化操作和形式化的准确性,同时利用细化求精操作建立体系结构的层次模型,有效解决了状态空间爆炸问题。此外,在求精过程中为了保证用于下层求精的子网能准确表达上层行为规约,引入了进程代数来刻画Petri网的行为语义。最后,给出了进程项构造子网的算法及案例研究,并通过开源工具验证上述内容的正确性。     

Compositional Action System Refinement

We show how a parallel composition of action systems can be refined by refining the components separately, and checking non-interference against invariants and guarantee conditions, which are abstract and stable. The guarantee condition can be thought of as a very abstract specification of how a system affects the global state, and it allows us to show that an action system refinement is valid in a given environment, even if we do not know any of the details of that environment. The paper extends the traditional notion of action systems slightly, and it makes use of a generalisation of the attribute model for program variables.     

Refinement and coarsening of surface meshes

This paper presents an adaptation scheme for surface meshes. Both refinement and coarsening tools are based upon local retriangulation. They can maintain the geometric features of the given surface mesh and its quality as well. A mesh gradation tool to smooth out large size differences between neighboring (in space) mesh faces and a procedure to detect and resolve self-intersections in the mesh are also presented. Both are driven by an octree structure and make use of the presented refinement tool.     

Refinement via Consistency Checking in MDA

Refinement is a key practice in the Model-Driven Architecture initiative of the Object Modelling Group. However, the practice is loosely defined, overloaded, and open to misinterpretation. In this paper, we outline ongoing work on providing a precise definition for refinement via consistency checking, not only in the context of MDA, but more generally for model-driven development in a variety of domains.     

A singleton failures semantics for Communicating Sequential Processes

This paper defines a new denotational semantics for the language of Communicating Sequential Processes (CSP). The semantics lies between the existing traces and failures models of CSP, providing a treatment of non-determinism in terms of singleton failures. Although the semantics does not represent a congruence upon the full language, it is adequate for sequential tests of non-deterministic processes. This semantics corresponds exactly to a commonly used notion of data refinement in Z and Object-Z: an abstract data type is refined when the corresponding process is refined in terms of singleton failures. The semantics is used to explore the relationship between data refinement and process refinement, and to derive a rule for data refinement that is both sound and complete. Received October 2001 Revised September 2002, February 2003, June 2004 and October 2005 Accepted November 2005 by I. J. Hayes     

A Logic for Schema-Based Program Development

We show how a theory of specification refinement and program development can be constructed as a conservative extension of our existing logic for Z. The resulting system can be set up as a development method for a Z-like specification language, or as a generalisation of a refinement calculus (with a novel semantics). In addition to the technical development we illustrate how the theory can be used in practice.     

Refinement is complete for implementations

Modal transition systems specify sets of implementations, their refining labelled transition systems, through Larsen & Thomsen’s co-inductive notion of refinement. We demonstrate that refinement precisely captures the identification of a modal transition system with its set of implementations: refinement is reverse containment of sets of implementations. This result extends to models that combine state and event observables and is drawn from a SFP-domain whose elements are equivalence classes of modal transition systems under refinement [HJS04], and abstraction-based finite-model properties proved in this paper. As a corollary, validity checking is model checking for Hennessy-Milner formulas that characterize modal transition systems with bounded computation paths. We finally sketch how techniques developed in this paper can be used to detect inconsistencies between multiple modal transition systems and, if consistent, to verify properties of all common implementations.Received January 2004Revised August 2004Accepted December 2004 by M. Leuschel and D. J. Cooke     

关于Petri网精细化操作及其应用研究

为了解决“顾客投诉”等这一类业务处理问题,提出了用Petri网精细化操作解决问题的方案。定义了一种子网,用这种子网分别对Petri网中的某些变迁进行细化,得到更细致、更精确的Petri网。研究了Petri网精细化操作的性质保持问题,给出了这种精细化操作保持结构有界性、守恒性、可重复性、相容性和活性的充分条件。本文的结果可为复杂大系统的分析提供重要手段,并特别适合于一类业务系统的描述和验证,具有一定的实用价值。     

用Petri网描述程序精化中的循环不变式

形式化方法把程序看成规范,形式化开发方法包括形式规范和规范（程序）的精化。精化演算方法能够通过演算的方式,把规范逐步精化为程序。然而,演化的过程依赖于开发人员的经验,整个过程全部都是手动的。形式化方法的最高目标是软件自动化,使得能从规范自动开发出正确的程序。因而用Petri网来描述程序精化中的循环不变式,希望以此作为软件自动化的一个探索。     

A Note on the Refinement of Nonmonotonic Knowledge Bases

Refinement of logical theories plays an important role in various application domains, notably in software engineering. This note introduces and studies refinement notions for nonmonotonic knowledge bases in default logic. The paper motivates and proposes refinement concepts, discusses their relationship, and establishes sufficient conditions for refinement. Received 27 July 1999 / Revised 3 November 1999 / Accepted 24 May 2000