Discounting Infinite Games But How and Why?

In a recent paper de Alfaro, Henzinger and Majumdar [Luca de Alfaro, Thomas A. Henzinger, and Rupak Majumdar. Discounting the future in systems theory. In ICALP 2003, volume 2719 of LNCS, pages 1022–1037. Springer, 2003] observed that discounting successive payments, the procedure that is employed in the classical stochastic game theory since the seminal paper of Shapley [L.S. Shapley. Stochastic games. Proceedings Nat. Acad. of Science USA, 39:1095–1100, 1953], is also pertinent in the context of much more recent theory of stochastic parity games [L. de Alfaro and R. Majumdar. Quantitative solution to omega-regular games. In STOC'01, pages 675–683. ACM Press, 2001. final version to appear in Journal of Computer and System Sciences, L. de Alfaro, T.A. Henzinger, and O. Kupferman. Concurrent reachability games. In FOCS'98, pages 564–575. IEEE Computer Society Press, 1998, L. de Alfaro and T.A. Henzinger. Concurrent ω-regular games. In LICS'00, pages 142–154. IEEE Computer Society Press, 2000] which were proposed as a tool for verification of probabilistic systems. We show that, surprisingly perhaps, the particular discounting used in [Luca de Alfaro, Thomas A. Henzinger, and Rupak Majumdar. Discounting the future in systems theory. In ICALP 2003, volume 2719 of LNCS, pages 1022–1037. Springer, 2003] is in fact very close to the original ideas of Shapley. This observation allows to realize that the specific discounting of [Luca de Alfaro, Thomas A. Henzinger, and Rupak Majumdar. Discounting the future in systems theory. In ICALP 2003, volume 2719 of LNCS, pages 1022–1037. Springer, 2003] suffers in fact from some needless restrictions. We advocate that dropping the constraints imposed in [Luca de Alfaro, Thomas A. Henzinger, and Rupak Majumdar. Discounting the future in systems theory. In ICALP 2003, volume 2719 of LNCS, pages 1022–1037. Springer, 2003] leads to a more general and elegant theory that includes parity and mean payoff games as particular limit cases.     

A Contract-based Approach to Specifying and Verifying Safety Critical Systems

Light-weight formal method has been regarded as an important approach to development of component-based safety critical systems. The paper proposes an approach which can formally specify and verify the contract of static structure, dynamic behavior and refinement of component systems based on UML 2.0 superstructure. As results, the correctness of static contract can be obtained via type checking of interfaces and connectors. Dynamic contract can be verified through determining the cooperativeness of integrated components, whose contracts are depicted with interface protocol state machines and their semantics models, namely contract automata. The refinement relation between high level component and its implementation will be guaranteed through defining the alternating simulation between contract automata of components at different levels.     

构件式实时系统建模与验证研究

在复杂的实时系统开发中使用构件式设计方法已成为目前软件开发领域中的研究热点,如何有效地验证实时软件的设计是否满足给定的时间需求并降低验证过程的复杂度,是实时计算领域中的主要挑战之一.文中对构件接口模型进行时间扩展,提出了时间接口模型,并将其用于构件接口交互行为的形式化建模.在接口自动机理论的的基础上进一步提出了时间接口自动机模型用于描述时间接口交互下构件的行为及组合方法,通过消除错误状态产生组合模型来约减构件时间接口自动机模型的积,并在约减的模型上进行性质检验,降低了分析复杂度,有效地应对状态空间爆炸问题.为了说明论文建议的方法,详细讨论了一个简单的、贯穿整篇论文的示例系统.     

Formal verification of components assembly based on SysML and interface automata

We propose an approach which combines component SysML models and interface automata in order to assemble components and to verify formally their interoperability. So we propose to verify formally the assembly of components specified with the expressive and semi-formal modeling language, SysML. We specify component-based system architecture with SysML Block Definition Diagram, and the composition links between components with Internal Block Diagrams. Component’s protocols are specified with sequence diagrams, they are necessary to exploit interface automata formalism. Interface automata is a common Input Output (I/O) automata-based formalism intended to specify the signature and the protocol level of the component interfaces. We propose formal specifications for SysML semi-formal models in order to exploit interface automata approach. We also improve the interface automata approach by considering system architecture, specified with SysML, in the verification of components composition.     

Interface synthesis and protocol conversion

Given deterministic interfaces P and Q, we investigate the problem of synthesising an interface R such that P composed with R refines Q. We show that a solution exists iff P and are compatible, and the most general solution is given by , where is the interface P with inputs and outputs interchanged. Remarkably, the result holds both for asynchronous and synchronous interfaces. We model interfaces using the interface automata formalism of de Alfaro and Henzinger. For the synchronous case, we give a new definition of synchronous interface automata based on Mealy machines and show that the result holds for a weak form of nondeterminism, called observable nondeterminism. We also characterise solutions to the synthesis problem in terms of winning input strategies in the automaton , and the most general solution in terms of the most permissive winning strategy. We apply the solution to the synthesis of converters for mismatched protocols in both the asynchronous and synchronous domains. For the asynchronous case, this leads to automatic synthesis of converters for incompatible network protocols. In the synchronous case, we obtain automatic converters for mismatched intellectual property blocks in system-on-chip designs. The work reported here is based on earlier work on interface synthesis in Bhaduri (Third international symposium on automated technology for verification and analysis, ATVA 2005, pp 338–353, 2005) for the asynchronous case, and Bhaduri and Ramesh (Sixth international conference on application of concurrency to system design, ACSD 2006, pp 208–216) for the synchronous one.     

Alternating-time stream logic for multi-agent systems

Constraint automata have been introduced to provide a uniform operational model for specifying service interfaces of components, the network that yields the glue code for the components, and the operational behavior of the composite system. Constraint automata have been used as the basis for equivalence checking and model checking temporal logical properties. This paper presents a multi-player semantics for constraint automata which serves to reason about controllability, interaction and cooperation facilities of individual components or coalitions of components in a given network. We introduce a temporal logic framework, called alternating-time stream logic, that combines classical features of alternating-time logic (ATL) for concurrent games with special operators for specifying regular conditions on the data streams in the network and on the write and read operations at the I/O-ports of the components. Since constraint automata support any kind of synchronous and asynchronous peer-to-peer communication, the resulting game structure is non-standard and requires a series of nontrivial adaptations to the semantics and verification algorithms for classical alternating-time approaches.     

MOG user interface builder: a mechanism for integrating application and user interface

Tools which provide graphical editing techniques for the design of user interface presentations are increasingly commonplace. Such tools vary widely in the mechanisms used to define user interfaces and while some are general purpose, others are targeted at particular application domains. Designers faced with varying requirements must choose one tool and live with its shortcomings, purchase a number of different tools, or implement their own. The paper describes an approach to facilitating the latter by providing a library of augmented user interface components called MOG objects which embody both end-user and editing semantics. User interface design tools based on this approach need only provide mechanisms for composing MOG objects into user interfaces and the addition of any other, higher-level functionality. MOG-based user interfaces retain an in-built editing capability and are inherently tailorable.     

An approach to automatic adaptation of assembly models

Adaptation plays a fundamental role in case-based design. However, after decades of efforts, automatic adaptation is still an open issue. In works of case-based design, a designer usually chooses a start-up product model (a candidate model) of moderate complexity based on a query model possessing primary new design requirements (kinematic semantics and geometry), then achieves the target design by adapting the candidate model according to the new design requirements and human interventions are often indispensable. To smartly adapt the candidate model to fit the new design requirements, a novel approach to automatic adaptation of assembly models is proposed in this paper. First, in order to effectively identify the corresponding links and interfaces between two non-preregistered assembly models as relevant elements, an attributed kinematic graph is put forward and adopted. Second, based on the attributed kinematic graph, the kinematic semantics of the candidate model is automatically adapted to that of the query model. Third, through performing interface layout transferring, the geometry of the candidate model is automatically adapted to that of the query model based on the corresponding links and interfaces. A prototype system is also implemented to verify the effectiveness of the proposed approach.     

Interface theories for concurrency and data

We present a compositional approach for specifying concurrent behavior of components with data states on the basis of interface theories. The dynamic aspects of a system are specified by modal input/output automata, whereas changing data states are specified by pre- and postconditions. The combination of the two formalisms leads to our notion of modal input/output automata with data constraints (MIODs). In this setting we study refinement and behavioral compatibility of MIODs. We show that compatibility is preserved by refinement and that refinement is compositional w.r.t. synchronous composition, thus satisfying basic requirements of an interface theory. We propose a semantic foundation of interface specifications where any MIOD is equipped with a model-theoretic semantics describing the class of its correct implementation models. Implementation models are formalized in terms of guarded input/output transition systems and the correctness notion is based on a simulation relation between an MIOD and an implementation model which relates not only abstract and concrete control states but also (abstract) data constraints and concrete data states. We show that our approach is compositional in the sense that locally correct implementation models of compatible MIODs compose to globally correct implementations, thus ensuring independent implementability.     

接口自动机--一种用于组件组合的形式系统

接口自动机是描述基于组件系统中组件及组件间交互行为的形式化工具。接口自动机在处理组件组合问题时所使用的“乐观方法”和博弈思想是区别于其它形式化工具的关键点。本文对接口自动机、时间接口自动机和资源接口及其中的博弈思想进行综述。在同其它形式化方法比较的基础上,指出了接口自动机的长处和局限。文中总结了接口自动机在理论上和实际中的意义并对其应用前景做了展望。     

Approach to improving network capable application processor based on IEEE 1451 standard

The IEEE 1451 standard supports the structure of distributed data acquisition systems and networks. The key components for such a distributed network are the Network Capable Application Processor (NCAP), Smart Transducer Interface Module (STIM), and the communication interface between them. This paper proposes an approach to improve the NCAP by introducing the functions of on-line dynamic reprogramming of the NCAP and software-programmable interface to support the most widely used communication interfaces between the NCAP and STIM via the network. Experimental research results of the proposed approach applying software-programmable interfaces, application examples of the proposed NCAP, and benefits of the applications are presented in the paper.     

一种基于构件演算的主动构件精化方法

现代构件系统通常包含多个并发执行的主动构件,这使得验证构件系统的正确性变得十分困难.通过对构件演算进行扩展,提出了一种主动构件的精化方法.在构件接口层引入契约.契约使用卫式设计描述公共方法和主动活动的功能规约.通过一对发散、失败集合定义契约的动态行为,并利用发散、失败集合之间的包含关系定义契约间的精化关系.证明了应用仿真技术确认契约精化关系的定理.定义构件的语义为其需求接口契约到其服务接口契约的函数,以此为基础,可以通过契约的精化来证明构件的精化.给出了构件的组装规则.在构件系统自底向上的构造过程中,应用构件的精化方法和组装规则可以保证最终系统的正确性.     

Instrument semiotics: a semiotic approach to interface components

This paper will briefly present a semiotic approach to instrument interfaces based on a conceptual analysis of display and control components and their compositional semantics. Display and control components can be considered as prototypical objects that are themselves constructed from combinations of more elementary signs expressed in some combination of media. Different types of signs (or ‘representational modalities’) and different types of media have different semantic and syntactic properties. These properties will to some extent determine what different combinations of media and signs are good for, i.e. what kinds of information can be adequately expressed in a given media–modality combination, and what kinds of cognitive support it will give to the social agents using it in a work context. The relevance of such an approach is partly in enhancing our understanding of instrument interfaces and human–machine interaction in complex work domains and partly to support the design and development of flexible and tailorable instrument interfaces.     

A component framework for system modeling based on high-level replacement systems

The aim of this paper is to present a generic component framework for system modeling that satisfies main requirements for component-based development in software engineering. In this sense, we have defined a framework that can be used, by providing an adequate instantiation, in connection with a large class of semi-formal and formal modeling techniques. Moreover, the framework is also flexible with respect to the connection of components, providing a compositional semantics of components. This means more precisely that the semantics of a system can be inferred from the semantics of its components. In contrast to other component concepts for data type specification techniques, our component framework is based on a generic notion of transformations. In particular, refinements and transformations are used to express intradependencies, between the export interface and the body of a component, and interdependencies, between the import and the export interfaces of different components. The generic component framework generalizes module concepts for different kinds of Petri nets and graph transformation systems proposed in the literature, and seems to be also suitable for visual modeling techniques, including parts of the UML, if these techniques provide a suitable refinement or transformation concept. In this paper the generic approach is instantiated in two steps. First to high-level replacement systems generalizing the transformation concept of graph transformations. In a second step it is further instantiated to low-level and high-level Petri nets. To show applicability we present sample components from a case study in the domain of production automation as proposed in a priority program of the German Research Council (DFG).     

一种服务消息交互行为的元建模方法

为了提高服务消息接口的规范性和交互行为的正确性,提出了一种服务消息交互的元建模方法。基于工作流模型对服务进行建模,通过对消息操作模式予以分析,给出了接口形式化表示和接口相容性检查方法。采用推理规则和递归函数刻画消息传递的语义,讨论了服务交互时各种环境的变化情况。实例分析表明,该方法可以规范服务接口模式,有效地对消息的交互情景进行建模,进而保障服务建模的可靠性。     

Continuity controlled hybrid automata

We investigate the connections between the process algebra for hybrid systems of Bergstra and Middelburg and the formalism of hybrid automata of Henzinger et al. We give interpretations of hybrid automata in the process algebra for hybrid systems and compare them with the standard interpretation of hybrid automata as timed transition systems. We also relate the synchronized product operator on hybrid automata to the parallel composition operator of the process algebra. It turns out that the formalism of hybrid automata matches a fragment of the process algebra for hybrid systems closely. We present an adaptation of the formalism of hybrid automata that yields an exact match.     

UML顺序图与状态图的一致性检查

用户可使用UML从不同角度对系统进行建模,但不同视图间存在信息冗余,可能导致视图不一致问题。该文针对具有多种逻辑语义的顺序图提出分析方法,为复杂层次结构的状态图引入有限状态自动机,利用自动机分解算法得到自动机树。制定新的顺序图和状态图一致性检查准则和Promela代码结构,用模型检验工具SPIN进行顺序图及其相关状态图的一致性检验。     

场景驱动的构件行为舍弃

如果构件含有冗余的行为,特别是有用户不想要的功能,则用户无法使用。因此,如何从构件中保留场景规约中用户需要的行为便是一个亟待解决的问题。给出了一种解决方法。该方法通过舍弃用户不需要的行为,保留场景规约中用户需要的行为,得到一个用户可以使用的构件。用带注释的接口自动机为构件的行为建模,用带注释的消息序列图(MSC)描述场景规约,给出了基于场景进行构件行为舍弃的方法。并用一个实例对文中所述的方法进行了说明。