10148394
Generating C Code from LOGS Specifications
This paper introduces a tool that automatically translates a concrete form of specifications into C code linked with BSPlib. The translation tool is rigorously developed with important safety properties proved. A Logs specification for Bulk-Synchronous Parallelism is a relation of an initial state, a final state and some intermediate states. Nondeterminism and parallelism correspond to disjunction and conjunction respectively. Various advanced specification commands can be derived from the basic ones. The translator checks syntax, freedom of communication interference, type consistency and communication dependencies before generating the target code. Static analysis (including both static checkings and translation) is presented in abstract interpretation. It is shown that a few laws are complete for transforming any specification into a normal form. These laws are satisfied by the abstract functions. We demonstrate the actual effects of the abstract functions by applying them on the normal form. The approach has been implemented using an object-oriented language.
15321284
From Durational Specifications to TLA Designs of Timed Automata
Different temporal logics tend to emphasise different aspects of a hybrid system. In this paper, we study the predicative interpretation of Duration Calculus (DC) and Temporal Logic of Actions (TLA) and the link between them. A notation called generic composition is used to simplify the manipulation of predicates. The modalities of possibility and necessity become generic composition and its inverse of converse respectively. The transformation between different temporal logics is also characterised as such modalities. The formalism provides a framework in which human experience about hybrid system development can be formalised as refinement laws. A high-level durational specification can be decomposed to two durational specifications driven by an automaton. In such a stepwise design process, durational features are reduced while automaton features increase gradually. The application of the technique is demonstrated in the case study of the gas burner problem.
17662809
Hierarchical Organisation of Predicate-Semantic Models
This paper introduces techniques to organise predicate- semantic models in a hierarchical structure so that a new model can inherit the laws of the existing ones. Generic composition is used to simplify the manipulation of predicates. Necessary restrictions are imposed on the definition of each model so that the inheritance relation can be established by checking a few conditions on the healthiness conditions and the commands. Much of the checking can be supported by laws of generic composition. The techniques also help simplify the proof of well-definedness of program combinators (i.e. their closure in the semantic space) so that we no longer need to prove it (in predicate calculus) for every new model.
1010133
A fixpoint theory for non-monotonic parallelism
This paper studies parallel recursion. The trace specification language used in this paper incorporates sequentiality, nondeterminism, reactiveness (including infinite traces), three forms of parallelism (including conjunctive, fair-interleaving and synchronous parallelism) and general recursion. In order to use Tarski’s theorem to determine the fixpoints of recursions, we need to identify a well-founded partial order. Several orders are considered, including a new order called the lexical order, which tends to simulate the execution of a recursion in a similar manner as the Egli-Milner order. A theorem of this paper shows that no appropriate order exists for the language. Tarski’s theorem alone is not enough to determine the fixpoints of parallel recursions. Instead of using Tarski’s theorem directly, we reason about the fixpoints of terminating and nonterminating behaviours separately. Such reasoning is supported by the laws of a new composition called partition. We propose a fixpoint technique called the partitioned fixpoint, which is the least fixpoint of the nonterminating behaviours after the terminating behaviours reach their greatest fixpoint. The surprising result is that although a recursion may not be lexical-order monotonic, it must have the partitioned fixpoint, which is equal to the least lexicalorder fixpoint. Since the partitioned fixpoint is well defined in any complete lattice, the results are applicable to various semantic models. Existing fixpoint techniques simply become special cases of the partitioned fixpoint. For example, an Egli-Milnermonotonic recursion has its least Egli-Milner fixpoint, which can be shown to be the same as the partitioned fixpoint. The new technique is more general than the least Egli-Milner fixpoint in that the partitioned fixpoint can be determined even when a recursion is not Egli-Milner monotonic. Examples of non-monotonic recursions are studied. Their partitioned fixpoints are shown to be consistent with our intuition.
8852685
Generic Composition
Abstract. This paper presents a technique called generic composition to provide a uniform basis for modal operators, sequential composition, different kinds of parallel compositions and various healthiness conditions appearing in a variety of semantic theories. The weak inverse of generic composition is defined. A completeness theorem shows that any predicate can be written in terms of generic composition and its weak inverse. A number of algebraic laws that support reasoning are derived.
13475813
Compositional Reasoning for Pointer Structures
This paper studies the compositional definition and behaviour of properties that arise in pointer structures. A pointer structure is represented as a (pointer) graph. A pointer property is a set of pointer structures. A parameterised binary combinator is defined that enables important properties (like acyclicity, canonicity and reachability) to be defined in a compositional manner. The technique of parameterising a combinator derives from the definition of parallel-by-merge in ‘Unifying Theories of Programming'. It is applied here to the study of disjointness combinators that extend the separating conjunction of Separation Logic. A case study is provided to demonstrate how these ideas are used, in the form of rules of Hoare logic, to verify the correctness of an Object-Oriented program.
28100130
Global Software Enterprise: A New Software Constructing Architecture
Based on current service-oriented architecture (SOA), this paper introduces a consumer-oriented SOA software constructing architecture: the global software enterprise (GSE) architecture. In this architecture, the software construction starts from the consumers' publishing their requirements in the form of application or service specification which they exactly want. The consumer also publishes the expectation for the services the application needs in the form of collaboration specification and test scripts. The service providers then produce services that meet the needs of the applications. This new approach reduces the workload for the consumer and the communication between the consumer and provider. It also extends the design and code sharing, and thus further improves the software productivity
2016418
CHIME: customizable hyperlink insertion and maintenance engine for software engineering environments
Source code browsing is an important part of program comprehension. Browsers expose semantic and syntactic relationships (such as between object references and definitions) in GUI-accessible forms. These relationships are derived using tools which perform static analysis on the original software documents. Implementing such browsers is tricky. Program comprehension strategies vary, and it is necessary to provide the right browsing support. Analysis tools to derive the relevant cross-reference relationships are often difficult to build. Tools to browse distributed documents require extensive coding for the GUI, as well as for data communications. Therefore, there are powerful motivations for using existing static analysis tools in conjunction with WWW technology to implement browsers for distributed software projects. The CHIME framework provides a flexible, customizable platform for inserting HTML links into software documents using information generated by existing software analysis tools. Using the CHIME specification language, and a simple, retargetable database interface, it is possible to quickly incorporate a range of different link insertion tools for software documents, into an existing, legacy software development environment. This enables tool builders to offer customized browsing support with a well-known GUI. This paper describes the CHIME architecture, and describes our experience with several re-targeting efforts of this system.
17642380
Evolutionary Modeling of Ordinary Differential Equations for Dynamic Systems
This paper presents a new idea of modeling one-dimensional dynamic systems by higher-order ordinary differential equation (HODE) models in stead of by the ARMA models used in the traditional time series analysis. Accordingly, based on the idea of hybrid evolutionary modeling, we modify the HEMA algorithm in (Cao et al., 1998a; Cao et al., 1998b) to approach the modeling problem of HODEs for dynamic systems. Two applications of time series are used to demonstrate its effectiveness and advantages.
44397360
Reducing Time Complexities of Semigroup Computations on Mesh-Connected Computers with Multiple Broadcasting
8311095
Classifying image texture with statistical landscape features
This paper proposes to use three-dimensional information derived from the graph of an image function for texture description. The graph of an image function is a rumpled surface appearing like a landscape. To characterize the texture through this landscape, six novel texture feature curves based on the statistics of the geometrical and topological properties of the solids shaped by the graph and a variable horizontal plane are used. The proposed statistical landscape features have been shown by systematic experiments to offer very low error rates on a large subset of the Brodatz texture album having excluded some nonhomogeneous images, the entire Brodatz texture set, as well as the VisTex texture collection.