Complex-network theory is a new approach in studying different types of large systems in both the physical and the abstract worlds. In this paper, we have studied two kinds of network from software engineering: the component dependence network and the sorting comparison network (SCN). It is found that they both show the same scale-free property under certain conditions as complex networks in other fields. These results suggest that complex-network theory can be a useful approach to the study of software systems. The special properties of SCNs provide a more repeatable and deterministic way to study the evolution and optimization of complex networks. They also suggest that the closer a sorting algorithm is to the theoretical optimal limit, the more its SCN is like a scale-free network. This may also indicate that, to store and retrieve information efficiently, a concept network might need to be scale-free.

Complex-network theory is a new approach in studying different types of large systems in both the physical and the abstract worlds. In this paper, we have studied two kinds of network from software engineering: the component dependence network and the sorting comparison network (SCN). It is found that they both show the same scale-free property under certain conditions as complex networks in other fields. These results suggest that complex-network theory can be a useful approach to the study of software systems. The special properties of SCNs provide a more repeatable and deterministic way to study the evolution and optimization of complex networks. They also suggest that the closer a sorting algorithm is to the theoretical optimal limit, the more its SCN is like a scale-free network. This may also indicate that, to store and retrieve information efficiently, a concept network might need to be scale-free.

To ensure correct implementation of complex access control requirements, it is important that the validated and verified requirements are effectively integrated with the rest of the system. It is also important that the system can be validated and verified early in the development process. In this paper we present an integrated, role-based access control model. The model is based on the graphical behavior tree notation, and can be validated by simulation, as well as verified using a model checker. Using this model, access control requirements can be integrated with the rest of the system from the outset, because: a single notation is used to express both access control and functional requirements; a systematic and incremental approach to constructing a formal behavior tree specification can be adopted; and the specification can be simulated and model checked. The effectiveness of the model is evaluated using a case study with distributed access control requirements.

Constraints allow users to declare relationships among objects and let the constraint systems maintain and satisfy these relationships. Formulas have been adopted to express constraints in a wide variety of single-user applications, because of their simplicity, efficiency and manageability. The needs and benefits of supporting formula-defined constraints in collaborative environments have long been recognized. However, maintaining both constraints and consistency in the presence of concurrency in collaborative systems is a challenge. In these systems, users may concurrently define formulas, which could result in that different formulas are defined to express the same object attribute at different sites. In this article, we discuss the issues and techniques in maintaining formula-defined constraints in collaborative systems. In particular, we also proposed a method that is able to maintain both constraints and system consistency in concurrent environments based on the existing consistency maintenance approaches. This method extends the application of these approaches from collaborative systems without constraint to systems that support formulas. The proposed method has been applied to implement a collaborative Visio system, called CoVisio, which leverages single-user Microsoft Visio for multi-user collaboration. Specific issues related to CoVisio are also discussed in detail.

Recent advancements in collaboration technology have shown that it is possible to convert existing single-user applications into real-time collaborative applications without modifying the source codes of the single-user applications. Such conversion relies on the API (Application Programming Interface) provided by the single-user applications. Poorly designed APIs make such conversion difficult, inefficient, or even impossible. Until now, it is not well understood what features APIs should provide to facilitate conversion of single-user applications into collaborative applications. This paper presents recommendations of the features single-user application APIs should provide to facilitate conversion. The results are based on what we have learnt from converting Microsoft Visio, into real-time collaborative Visio (CoVisio), and our previous experience in building CoWord and CoPowerPoint.

Constraints are very useful in real-time collaborative editing systems. They are able to automatically enforce semantic rules and properties. A specific type of constraint is dataflow constraint. Any property that can be expressed as an equation can be represented as a dataflow constraint. However, ensuring multi-way dataflow constraint satisfaction and consistency maintenance in a replicated collaborative environment is a challenge. This paper presents a novel method for computing multi-way dataflow constraint propagation for real-time collaborative editing systems. This method produces convergent result that is consistent with syntax level effect, irrespective of the operation execution order. This method is generic and is applied to enforce object placement and label name consistency in a realtime collaborative CASE system

Most modern embedded systems are now required to satisfy seemingly divergent critical properties like safety and security. It is therefore becoming increasingly important that any systems development methodology employed should support modeling of system requirements in a manner that it facilitates validation and verification of such critical properties. In the paper we present the result of applying the genetic software engineering (GSE) method to design an ambulatory infusion pump (AIP) which must satisfy a number of safety and security properties. The safety and security requirements are integrated with the rest of the systems requirements in the form of integrated behavior tree (IBT), which is systematically refined into a design behavior tree (DBT). The integrated behavioral view of the requirements provides a platform for requirements conflict resolution, defect detection and requirements validation. The formal semantics of the behavior tree (BT) notation, used to specify the requirements, makes formal verification of critical properties in the final design possible.

Multi-way dataflow constraints are very useful in the development of collaborative applications, such as collaborative CAD and CASE systems, but satisfying multi-way dataflow constraints in the presence of concurrency in collaborative systems is difficult. In this article, we discuss the issues and techniques in maintaining multi-way dataflow constraints in concurrent environments. In particular, we also proposed a novel strategy that is able to reconstruct computation flows to satisfy multi-way dataflow constraints according to concurrent user operations in collaborative systems. Our strategy ensures both constraint satisfaction and system consistency, which is independent of the execution orders of concurrent operations.

Despite the advances in software engineering since 1968, current methods for going from a set of functional requirements to a design are not as direct, repeatable and constructive as we would like. Progress with this fundamental problem is possible once we recognize that individual functional requirements represent fragments of behavior, while a design that satisfies a set of functional requirements represents integrated behavior. This perspective admits the prospect of constructing a design out of its requirements. A formal representation for individual functional requirements, called behavior trees makes this possible. Behavior trees of individual functional requirements may be composed, one at a time, to create an integrated design behavior tree. From this problem domain representation it is then possible to transition directly and systematically to a solution domain representation of the component architecture of the system and the behavior designs of the individual components that make up the system - both are emergent properties.

We address the problem of transforming natural language descriptions of contracts into a form that is suitable for automating various contract management functions. We investigate two complementary methods that can be used to achieve this. One method is suitable for the contract specification phase - to specify expected behaviour of contracting parties so that they can satisfy policies stated in a contract. This method also allows for checking aspects of contract consistency as well as flexible integration of internal organisational policies with the contract policies. Another method targets the contact run-time phase - for monitoring behaviour of parties to the contract and other aspects of contract performance. When combined, these two methods provide a basis to support an increasing level of automation of many mundane contract activities, while allowing humans to be involved in ultimate decision making.

Loops with multiple-exits and flags detract from the quality of imperative programs. They tend to make control-structures difficult to understand and, at the same time, introduce the risk of non-termination and other correctness problems. A systematic, generally applicable procedure, called loop rationalization, which removes such features and logically simplifies loop structures is presented. This method, which is founded on the principle of separation of concerns, employs strongest postcondition calculations and congruent equivalence transformations to improve loops. A by-product of the process is that it detects a range of defects such as unreachable code and a class of non-termination problems.

Goto statements detract from the quality of imperative programs. They tend to make control-structures difficult to understand and, at the same time, introduce the risk of non-termination and other correctness problems. A new, formal, generally applicable procedure for removing all goto statements from program structures is presented. This method is based on formal semantics and congruent equivalence transformations. Not only does the method logically simplify program structures; it also detects a range of defects including a class of non-termination problems, unreachable code and redundancy problems. The method can also be used to eliminate recursion.

Abstract Given a loop invariant, I , and an assignment, α , which decreases the variant, we define a constructive function, cg, called the co-invariant generator, which has the property that I Λ cg ( α, I ) ⇒ wp ( α, I ), where wp ( α, I ) is the weakest precondition for α to establish I. Several results about the co-invariant generator are proved, important special cases are considered, and a non-trivial example of its use in deriving the body of a loop is given. We also define a function which performs a related constructive action on terms formed from binary operations. The coinvariant generator makes a useful contribution to formalising and automating a key step in program derivation.

A model for software product quality is defined, it has been formulated by associating a set of quality-carrying properties with each of the structural forms that are used to define the statements and statement components of a programming language. These quality-carrying properties are in turn linked to the high-level quality attributes of the International Standard for Software Product Evaluation ISO-9126. The model supports building quality into software, definition of language-specific coding standards, systematically classifying quality defects, and the development of automated code auditors for detecting defects in software.>

A method for handling boundary structure clashes is presented. It provides a simple alternative to Jackson's program inversion technique. It is a constructive approach based on the use of prototypes. Development begins by solving the corresponding simpler problem that has no structure clashes. This solution is then used to guide the solution of the original problem. Programs constructed in this way preserve the correspondence between the program control structure and the data structure. They should therefore be easier to maintain than their counterparts developed using Jackson's program inversion method.

A constructive method of program development is presented. It is based on a simple strategy for problem decomposition that is claimed to be more supportive of goal-oriented programming than the Wirth-Dijkstra top-down refinement method. With the proposed method, a program is developed by making a sequence of refinements, each of which can establish the postcondition for a corresponding sequence of progressively weaker preconditions until a mechanism has been composed that will establish the postcondition for the original given precondition for the problem. The strategy can minimize case analysis, simplify constructive program proofs, and ensure a correspondence between program structure and data structure.>

It is important to be able to derive different algorithms that meet a particular specification. Transformations on a program specification provide a systematic means for such an endeavour. Different transformations on a specification can yield new and alternative forms of invariants. These invariants, in turn, can provide the framework for the derivation of a variety of algorithms by the use of weakest precondition techniques. To demonstrate these ideas a number of well-known sorting algorithms are shown to be derivable from a single original program specification. The intelligent use of equivalent forms is the touchstone of logical insight (S. K. Langer).

Abstract A refinement to a well‐known selection algorithm is described. The refinement results in a useful improvement in the performance of the original algorithm, particularly when the selection index is small relative to the median.

Abstract A constructive method of program development is presented. It seeks to unify two important ideas about program development. Namely that programming is a goal‐oriented activity and that there should be a correspondence between data and program structures. The latter concept is seen to be extensible beyond the data processing context in which it was originally proposed. Induction provides the vehicle for program development by stepwise refinement, with the final program being constructed by application of a sequence of progressively more powerful generalizations. The design process employed guarantees the correctness of the final program provided that each of the refinement steps have been correctly taken. The method is illustrated by a number of samples.

Abstract Loops must often be forced to terminate early. Solutions to such problems are usually either language‐dependent or rather clumsy. A practical alternative is presented. The accompanying methodology clarifies the role of the finalization mechanism in loop construction. It also leads to the idea of control‐structure independence in the context of data representation and forced termination.

Abstract The widely known Quicksort algorithm does not attempt to actively take advantage of partial order in sorting data. A simple change can be made to the Quicksort strategy to give a bestcase performance of n, for ordered data, with a smooth transition to O(n log n) for random data. This algorithm (Transort) matches the performance of Sedgewick's claimed best implementation of Quicksort for random data.