Integrating predicate transition nets with first order temporal logic in the specification and verification of concurrent systems

This paper presents some results of integrating predicate transition nets with first order temporal logic in the specification and verification of concurrent systems. The intention of this research is to use predicate transition nets as a specification method and to use first order temporal logic as a verification method so that their strengths — the easy comprehension of predicate transition nets and the reasoning power of first order temporal logic can be combined. In this paper, a theoretical relationship between the computation models of these two formalisms is presented; an algorithm for systematically translating a predicate transition net into a corresponding temporal logic system is outlined; and a special temporal refutation proof technique is proposed and illustrated in verifying various concurrent properties of the predicate transition net specification of the five dining philosophers problem.     

Multi-relations in Z

Both the theories of binary relations and multi-sets (or bags) in Z have been usefully applied to software specification and development. In this paper we examine a useful theory—multi-relations—which is a cross between these two theories. One way of viewing relations is as sets of pairs. Here, by analogy, we view multi-relations as multi-sets of pairs, and we define multirelation equivalents of most of the traditional operators defined on binary relations. Multi-relations can also be viewed as graphs or two-dimensional matrices (with indices over arbitrary sets).The use of multi-relations is illustrated by specifying a bill-of-materials system. This provides a good example of the paradigm of building a suitable mathematical theory first and then developing a specification in terms of the theory.     

关于软件需求中的不一致性管理

复杂软件系统开发的一个关键问题是分析和处理可能存在的不一致的需求描述.这个问题解决得好坏直接影响到需求规格说明的质量,进而影响到最终软件产品的质量.在目前公认的一个不一致需求管理框架的基础上,就需求不一致性管理方面的有代表性的工作,进行了较为系统的分析,以期建立对当前需求工程中,关于不一致的需求管理方法和技术的全面认识.最后,对需求不一致性管理方面的研究进行了展望.     

Mutation Testing Applied to Estelle Specifications

Many researchers have pursued the establishment of a low-cost, effective testing and validation strategy at the program level as well as at the specification level. Mutation Testing is an error-based approach, originally introduced for program testing, that provides testers a systematic way to evaluate how good a given test set is. Some studies have also investigated its use to generate test sets. In this article, the application of Mutation Testing for validating Estelle specifications is proposed. A mutant operator set for Estelle—one of the crucial points for effectively applying Mutation Testing—is defined, addressing: the validation of the behavior of the modules, the communication among modules and the architecture of the specification. In this scope, these operators can be taken as a fault model. Considering this context, a strategy for validating Estelle-based specification is proposed and exemplified using the Alternating-bit protocol.     

Prospec: Support for Elicitation and Formal Specification of Software Properties

Although formal verification techniques have been demonstrated to improve program dependability, software practitioners have not widely adopted them. One reason often cited is the difficulty in writing formal specifications. This paper introduces Prospec, a tool to assist practitioners in formally specifying software properties. Prospec uses property patterns and scopes. Previous efforts at providing tool support for property specification have not provided convenient abstractions for specifying properties that include multiple events or conditions. A taxonomy of composite propositions is introduced to address this issue by defining relations among propositions and providing graphical abstractions that can assist in specification and validation of properties. This paper shows how composite propositions can enhance the specification pattern system by helping practitioners consider subtleties of behavior in sequences and concurrency through directed questions and visual abstractions. The paper introduces an elicitation and specification process to define patterns, scopes, and composite propositions.     

Formal analysis of the Shlaer-Mellor method: Towards a toolkit of formal and informal requirements specification techniques

In this paper, we define a number of tools that we think belong to the core of any toolkit for requirements engineers. The tools are conceptual and hence, they need precise definitions that lay down as exactly as possible what their meaning and possible use is. We argue that this definition can best be achieved by a formal specification of the tool. This means that for each semi-formal requirements engineering tool we should provide a formal specification that precisely specifies its meaning. We argue that this mutually enhances the formal and semi-formal technique: it makes formal techniques more usable and, as we will argue, at the same time simplifies the diagram-based notations.At the same time, we believe that the tools of the requirements engineer should, where possible, resemble the familiar semi-formal specification techniques used in practice today. In order to achieve this, we should search existing requirements specification techniques to look for a common kernel of familiar semi-formal techniques and try to provide a formalisation for these.In this paper we illustrate this approach by a formal analysis of the Shlaer-Mellor method for object-oriented requirements specification. The formal specification language used in this analysis is LCM, a language based on dynamic logic, but similar results would have been achieved by means of another language. We analyse the techniques used in the information model, state model, process model and communication model of the Shlaer-Mellor method, identify ambiguities and redundancies, indicate how these can be eliminated and propose a formalisation of the result. We conclude with a listing of the tools extracted from the Shlaer-Mellor method that we can add to a toolkit that in addition contains LCM as formal specification technique.     

Modelling and validating the man-machine interface

This paper describes a formal model for expressing the functional requirements of the man-machine interfaces of interactive systems. It also shows how this model can facilitate the automation of other useful activities such as checking for inconsistency, redundancy, and incompleteness in the specification, and validating the implementation of the interface against its original requirements. Finally, the paper comments on the authors' experience in developing an interactive system using this formal model.     

基于XYZ/E规范的软件测试用例自动生成方法

针对软件规范输入域与被测软件输入域之间边界不一致引起的测试用例失效问题,提出一种基于时序逻辑语言XYZ／E软件规范说明的测试用例自动生成方法。该方法采用XYZ／E描述,首先确保规范与被测软件的语义一致,其次,利用XYZ／E规范的逻辑程序属性,实现了对测试用例中输出期望的Prolog自动推导求值。最后,通过一个实例验证了该方法的可行性。与传统方法相比,该方法既保证了软件测试用例的有效性,又减少了测试用例输出的计算工作量。     

基于企业流程的需求形式化验证技术

需求验证是为了确保需求规格说明具有良好特性(完整性、一致性、无二义性)而对需求规格说明进行的一种审查活动。目前广泛使用的需求验证技术存在着两个问题:难以处理大型、复杂的需求文档;审查过程需要相当长的时间。该文所研究的基于企业流程的需求形式化验证技术,通过对需求文档中企业流程各活动之间的逻辑关系进行验证,从而发现其中的不一致性和二义性。     

Z状态空间和操作定义的自动生成技术

从软件需求定义到形式功能堆约的自动转换是需求工程的重要问题之一。文中以软件需求定义语言ＮＤＲＤＬ和形式功能规给语言Ｚ为基础，探讨了基间的自动转换技术，特别是从ＮＤＲＤＬ需求定义自动获取Ｚ形式规约中状态空间与操作定义的技术。     

从BPMN模型导出组合服务的代数规约

针对应用规约自动测试BPEL表示组合服务时需要解决BPEL服务的规约生成问题,提出了一种从BPMN模型导出BPEL规范定义的组合Web服务的由代数规约语言CASOCC-WS表示的代数规约方法。首先,定义从BPMN模型转换成基调的规则和从BPMN结构转换成正则表达式的规则,设计由正则表达式导出构成公理的项的算法;然后,提出根据所得的项人工书写公理的启发式规则;最后,实现一个从BPMN模型导出组合服务基调的工具原型。案例研究表明,该方法可以解决BPEL服务的代数规约生成问题。     

A specification pattern for use cases

In this paper, general formats and guidelines are proposed, in an attempt to ameliorate the impact of frequently observed difficulties during the specification of use cases generated using “natural language” for the documentation of system functionality. The various writing styles derived from the multiple grammatical alternatives found in the Spanish language and the terminological diversity that characterises this language tend to reduce the clarity of text in a use-case specification. Thus, the purpose of its use in the different stages of development in a software system or component is seriously affected. However, even if this study has been made specifically for the Spanish language, it could be easily generalised to any language whose sentences are of the form subject/predicate. In order to control these problems, the use of a specification pattern supported by a series of guidelines on style and terminology is proposed for drafting use cases. Additionally, various degrees of refinement are suggested to guide specifiers towards obtaining a use case written according to this pattern.     

Initiative conflicts in task-oriented dialogue

An initiative conflict is an overlap of speech in which both conversants try to steer the conversation in different directions. In this paper, we investigate how conversants in human-human dialogue deal with such conflicts. First, in investigating why initiative conflicts occur, we find that the offsets of the utterances involved in initiative conflicts tend to be very short, and that initiative conflicts seem more likely to occur when one of the conversants has an urgent conversational goal. These findings strongly suggest that initiative conflicts are unintentional collisions and that conversants try to prevent them from even occurring, unless there is an urgent reason. Second, in investigating how initiative conflicts are resolved, we find that the overlaps tend to last less than two syllables, that volume correlates with who wins initiative conflicts, and that for longer overlaps, the volume of the winner increases in the second half of the overlaps. These findings strongly suggest that initiative conflicts are quickly resolved through an interactive process, using volume as one of the devices. Third, we find that after an initiative conflict is resolved, the winner sometimes repeats the words involved in the overlap; and this happens more when the overlap is more likely to interfere with the other conversant’s understanding. These findings will help us build next-generation mixed-initiative spoken dialogue systems that are natural and efficient to use.     

多媒体节目时序描述的组合技术

组合性是形式描述研究的基本问题,便于大型程序的设计、分析、测试和复用.为了方便用户编制大型多媒体系统的时序描述,组合模型是必须的.目前,这样的模型有基于语言的、基于图形的、基于时间区间的和面向对象的等等.但是,这些模型描述层次过低,很难支持两个多媒体节目之间的时序描述.通过引入单位流的概念和扩展两种时序关系,研究一种多媒体节目时序描述的结构化技术,使复杂的多媒体节目易于理解,以方便用户运用组合方法把一些可以复用于不同多媒体节目的节目模块进行组合设计.     

基于代数-时态逻辑的象形对象研究

本文首先讨论了国内外有关面向对象方法学、代数规范、时态逻辑的研究现状 ,分析了对象形式化语义研究的不足 .其次 ,分析了几种主要的系统形式化模型和方法 .然后 ,在我们已研究的“计算机甲骨文象形码输入法”的基础上 ,从时态逻辑的角度定义了象形对象及其约束条件 ,定义了面向对象的有色 Petri网 (OOPEN) ,并应用 OOPEN描述了象形对象的层次结构 .最后 ,我们将代数规范与时态逻辑相结合 ,对象形对象的语义基础进行了一些研究 .     

Specifying relations between research and the design of human-computer interactions

This paper argues the need for more effective: human-computer interactions; design of such interactions; and research to support such design. More effective research for design would result in more effective human-computer interactions. One contribution to more effective research would be the specification of relations between research and the design of human-computer interactions. The aim of this paper is to propose such a specification. Frameworks for specifying relations are proposed for: disciplines; the human-computer interaction (HCI) general design problem; and validation. The frameworks are used to model, and so to specify, the relations: between HCI research and the HCI general design problem; and within the particular scope of HCI, to support HCI research. Together, the models specify the relations between HCI research and the design of human-computer interactions. Meeting these specifications renders HCI knowledge coherent, complete and “fit-for-design-purpose”. An illustration of the relations, thus specified, is provided by a model of the planning and control of multiple task work in medical reception and its hypothetical application. The same frameworks are also used to specify the relations between Cognitive Science and the understanding of natural and artificial forms of intelligence. Lastly, they are further used to identify the relations not specified between Cognitive Science and the design of human-computer interactions. The absence of such relations renders Cognitive Science knowledge not coherent, complete nor “fit-for-design-purpose” (as opposed to “fit-for-understanding-purpose”). It is proposed how the relations specified for HCI and Cognitive Science might be used in the assessment of relations between other research and the design of human-computer interactions. Finally, the paper recommends that such an assessment should be undertaken by any discipline, such as Cognitive Science, which claims a relation between its research and the design of human-computer interactions. Such an assessment would establish whether or not such relations are, or can be, specified. The paper concludes that specification of relations is required for more effective research support for the design of human-computer interactions.     

A Formal Framework for Web Services Coordination

Recently the term Web Services Choreography has been introduced to address some issues related to Web Services Composition and Coordination. Several proposals for describing Choreography for Business Processes have been presented in the last years and many of these languages (e.g. BPEL4WS) make use of concepts as long-running transactions and compensations for coping with error handling. However, the complexity of BPEL4WS makes it difficult to formally define this framework, thus limiting the formal reasoning about the designed applications. In this paper, we formally address Web Services Coordination with particular attention to Web transactions. We enhance our past work - the Event Calculus - introducing two main novelties: i) a multicast event notification mechanism, and ii) event scope names binding. The former enables an easier specification of complex coordination scenarios — such as E-commerce applications require — while the latter allows many new interesting behaviors which can be very useful in business scenarios: the introduction of private event scope names — used to deal with security and privacy — and a dynamic event scopes definition that can be used to manage multiple instances of the same application.