Implementing IDEF techniques as simulation modelling specifications

Recent advantages in computer software have seen the introduction of powerful and easy-to-use simulation products, but unfortunately, still locking the ability to analyse real world problems in a high level terminology. A recent project undertaken for the company ATNS, forms the case study for demonstrating the merging of IDEF techniques and simulation modelling into meaningful business models.     

Process semantics for UML component specifications to assess inheritance

We define a component specification as a process. The starting point is the specification of a component in a UML profile. The process of the component is a derivable feature from the component specification. We define the inheritance of component specifications as inheritance of processes. Process semantics of the UML profile allows to check inheritance of specifications using a process algebra with renaming functions, we have presented.     

Implementing dynamic minimal-prefix tries

A modified trie-searching algorithm and corresponding data structure are introduced which permit rapid search of a dictionary for a symbol or a valid abbreviation. The dictionary-insertion algorithm automatically determines disambiguation points, where possible, for each symbol. The search operation will classify a symbol as one of the following: unknown (i.e. not a valid symbol), ambiguous (i.e. is a prefix of more than one valid symbol) or known. The search operation is performed in linear time proportional to the length of the input symbol, rather than the complexity of the trie. An example implementation is given in the C programming language.     

演绎对象数据库SD-DOOD中继承性的实现算法

介绍了演绎对象数据库SD DOOD系统的结构,给出了系统中可以实现的继承方法以及与实现这些方法有关的模式、实例、查询算法,并对算法的时间复杂度进行了分析。实验结果表明算法是可行的和有效的。     

Generating tests from B specifications and dynamic selection criteria

This paper is about generating tests from dynamic selection criteria called test purposes, in addition to structural tests, obtained from static selection criteria. We present a method that re-uses a behavioral model and an abstract test concretization layer developed for structural testing, and relies on additional test purposes. We propose, in the B framework, a process of test generation that uses the symbolic animation mechanisms of Leirios Test Generator (LTG) based on constraint solving, and guided by the test purposes. We build for that a B model that is the synchronized product of a behavioral B abstract model and a test purpose described as a labeled transition system. We prove the correctness of this method, and show some experimental results obtained on the IAS case study. IAS is an industrial smart-card platform dedicated to the operations of Identification, Authentication and electronic Signature. Our experiments show that the tests obtained from test purposes are complementary to the structural tests.     

Implementing set objects in dynamic distributed systems

This paper considers a set object, i.e., a shared object allowing users (processes) to add and remove elements to the set, as well as taking consistent snapshots of its content. Specifically, we show that there not exists any protocol implementing a set object, using finite memory, when the underlying distributed system is eventually synchronous and affected by continuous arrivals and departures of processes (phenomenon also known as churn). Then, we analyze the relationship between system model assumptions and object specification in order to design protocols implementing the set object using finite memory. Along one direction (strengthening the system model), we propose a protocol implementing the set object in synchronous distributed systems and, along the other direction (weakening the object specification), we introduce the notion of a k-bounded set object proposing a protocol working on an eventually synchronous system.     

Implementing agent teams in dynamic multiagent environments

Teamwork is becoming increasingly critical in multiagent environments ranging from virtual environments for training and education, to information integration on the internet, to potential multirobotic space missions. Teamwork in such complex, dynamic environments is more than a simple union of simultaneous individual activity, even if supplemented with preplanned coordination. Indeed, in these dynamic environments, unanticipated events can easily cause a breakdown in such preplanned coordination. The central hypothesis in this article is that for effective teamwork, agents should be provided explicit representation of team goals and plans, as well as an explicit representation of a model of teamwork to support the execution of team plans. In our work, this model of teamwork takes the form of a set of domain independent rules that clearly outline an agent's commitments and responsibilities as a participant in team activities, and thus guide the agent's social activities while executing team plans. This article describes two implementations of agent-teams based on the above principles, one for a realworld helicopter combat simulation, and one for the RoboCup soccer simulation. The article also provides a preliminary comparison of the two agent-teams to illustrate some of the strengths and weaknesses of RoboCup as a common test bed for multiagent systems.     

Implementing distributed and dynamic resource allocation in WATM

In this article a pragmatic approach for the dynamic resource allocation within the MAC layer of wireless ATM (WATM) networks is proposed. Emphasising ease of implementation and cost reduction, the protocols of MBS and Magic WAND are compared and evaluated. A novel MAC protocol called Distributed and Dynamic Resource Allocation (DADRA) is outlined. Central to this new scheme is the partial move of traffic prediction and computation into the mobile terminals, leaving the base station to co-ordinate media access based upon precise requests from the mobile terminals. The reduced processing demand on the base station may lower equipment costs and increase the number of supported connections.     

Constructing specifications by combining parallel elaborations

An incremental approach to construction is proposed, with the virtue of offering considerable opportunity for mechanized support. Following this approach one builds a specification through a series of elaborations that incrementally adjust a simple initial specification. Elaborations perform both refinements, adding further detail, and adaptations, retracting oversimplifications and tailoring approximations to the specifics of the task. It is anticipated that the vast majority of elaborations can be concisely described to a mechanism that will then perform them automatically. When elaborations are independent, they can be applied in parallel, leading to diverging specifications that must later be recombined. The approach is intended to facilitate comprehension and maintenance of specifications, as well as their initial construction     

Project management by configuration inheritance

Object-oriented programming apparently provides a great power to organise and manage all elements constituting a software project in a clean and efficient way. This is particularly not true, however, in a multiple project group-development circumstance. This paper presents an approach to solve these problems in a Smalltalk-type environment. Key ideas are configuration inheritance, version synthesis, and functionality mapping.     

Deriving protocol specifications from service specifications written in LOTOS

Summary.  A complete communication system is broken down into a number of protocol layers each of which provides services to the layer above it and uses services provided by its underlying layer. A service specification defines a particular ordering of the operations that a given layer provides to the layer above it. The active elements in each layer are called entities and they use a protocol in order to implement their service definition. On the basis of this relation between the service and protocol concepts we have developed algorithms for deriving protocol entity specifications from a formal service specification. The derived protocol entities ensure the correct ordering of the service primitives by exchanging synchronization messages through an underlying communication medium. This paper presents an extended version of our earlier derivation algorithms. This version of the algorithm can handle all operators and unrestricted process invocation and recursion as defined by basis LOTOS. The correctness of this derivation algorithm is formally proved. Received: January 1992 / Accepted: February 1996     

Type inference of SELF: Analysis of objects with dynamic and multiple inheritance

We have designed and implemented a type inference algorithm for the SELF language. The algorithm can guarantee the safety and disambiguity of message sends, and provide useful information for browsers and optimizing compilers. SELF features objects with dynamic inheritance. This construct has until now been considered incompatible with type inference because it allows the inheritance graph to change dynamically. Our algorithm handles this by deriving and solving type constraints that simultaneously define supersets of both the possible values of expressions and of the possible inheritance graphs. The apparent circularity is resolved by computing a global fixed-point, in polynomial time. The algorithm has been implemented and can successfully handle the SELF benchmark programs, which exist in the ‘standard SELF world’ of more than 40,000 lines of code.     

Crypt-equivalent algebraic specifications

Summary Equivalence is a fundamental notion for the semantic analysis of algebraic specifications. In this paper the notion of crypt-equivalence is introduced and studied w.r.t. two loose approaches to the semantics of an algebraic specification T: the class of all first-order models of T and the class of all term-generated models of T. Two specifications are called crypt-equivalent if for one specification there exists a predicate logic formula which implicitly defines an expansion (by new functions) of every model of that specification in such a way that the expansion (after forgetting unnecessary functions) is homologous to a model of the other specification, and if vice versa there exists another predicate logic formula with the same properties for the other specification. We speak of first-order crypt-equivalence if this holds for all first-order models, and of inductive crypt-equivalence if this holds for all term-generated models. Characterizations and structural properties of these notions are studied. In particular, it is shown that first order crypt-equivalence is equivalent to the existence of explicit definitions and that in case of positive definability two first-order crypt-equivalent specifications admit the same categories of models and homomorphisms. Similarly, two specifications which are inductively crypt-equivalent via sufficiently complete implicit definitions determine the same associated categories. Moreover, crypt-equivalence is compared with other notions of equivalence for algebraic specifications: in particular, it is shown that first-order cryptequivalence is strictly coarser than abstract semantic equivalence and that inductive crypt-equivalence is strictly finer than inductive simulation equivalence and implementation equivalence.     

Crypt-equivalent algebraic specifications

Summary Equivalence is a fundamental notion for the semantic analysis of algebraic specifications. In this paper the notion of “crypt-equivalence” is introduced and studied w.r.t. two “loose” approaches to the semantics of an algebraic specificationT: the class of all first-order models ofT and the class of all term-generated models ofT. Two specifications are called crypt-equivalent if for one specification there exists a predicate logic formula which implicitly defines an expansion (by new functions) of every model of that specification in such a way that the expansion (after forgetting unnecessary functions) is homologous to a model of the other specification, and if vice versa there exists another predicate logic formula with the same properties for the other specification. We speak of “first-order crypt-equivalence” if this holds for all first-order models, and of “inductive crypt-equivalence” if this holds for all term-generated models. Characterizations and structural properties of these notions are studied. In particular, it is shown that firstorder crypt-equivalence is equivalent to the existence of explicit definitions and that in case of “positive definability” two first-order crypt-equivalent specifications admit the same categories of models and homomorphisms. Similarly, two specifications which are inductively crypt-equivalent via sufficiently complete implicit definitions determine the same associated categories. Moreover, crypt-equivalence is compared with other notions of equivalence for algebraic specifications: in particular, it is shown that first-order cryptequivalence is strictly coarser than “abstract semantic equivalence” and that inductive crypt-equivalence is strictly finer than “inductive simulation equivalence” and “implementation equivalence”.     

Merging behavior specifications

This paper describes a method for merging behavior specifications modeled by transition systems. Given two behavior specificationsB1 andB2, Merge (B1,B2) defines a new behavior specification that extendsB1 andB2. Moreover, provided that a necessary and sufficient condition holds, Merge(B1,B2) is a cyclic extension ofB1 andB2. In other words, Merge (B1,B2) extendsB1 andB2, and any cyclic trace inB1 orB2 remains a cyclic in Merge(B1,B2). Therefore, in the case of cyclic traces ofB1 orB2, Merge(B1,B2) transforms into Merge(B1,B2), and may exhibit, in a recursive manner, behaviors ofB1 andB2. If Merge(B1,B2) is a cyclic extension ofB1 andB2, then Merge(B1,B2) represents the least common cyclic extension ofB1 andB2. This approach is useful for the extension and integration of system specifications.This research was supported by a grant from the Canadian Institute for Telecommunications Research under the NCE program of the Govemment of Canada and by an IBM research fellowship.     

Automated reformulation of specifications by safe delay of constraints

In this paper we propose a form of reasoning on specifications of combinatorial problems, with the goal of reformulating them so that they are more efficiently solvable. The reformulation technique highlights constraints that can be safely “delayed”, and solved afterwards. Our main contribution is the characterization (with soundness proof) of safe-delay constraints with respect to a criterion on the specification, thus obtaining a mechanism for the automated reformulation of specifications applicable to a great variety of problems, e.g., graph coloring, bin-packing, and job-shop scheduling. This is an advancement with respect to the forms of reasoning done by state-of-the-art-systems, which typically just detect linearity of specifications. Another contribution is an experimentation on the effectiveness of the proposed technique using six different solvers, which reveals promising time savings.