Behavioral Subtyping Relations for Active Objects

In this paper we investigate the object-oriented notion of subtyping in the context of behavioral formalisms. Behavioral formalisms are used to describe the dynamic behavior of active objects, viz. the protocols of interaction that active objects have to obey.Subtyping in OO-formalisms is closely related to the concept of inheritance. The central issue in the choice of subtyping relations among classes is the principle of substitutability: an instance of the subtype should be usable wherever an instance of the supertype was expected. Depending on the interpretation of usable, we obtain a variety of subtyping relations: stronger relations, allowing sharing of subtype instances among different clients, and weaker relations, restricting the possibilities of interference of different clients on the subtype instance. The subtyping relations are taxonomically ordered in a hierarchy. Substitutability is formalized via testing scenarios, which provide alternative characterizations for the subtyping relations.     

Coloured Petri net refinement specification and correctness proof with Coq

In this work, we address the issue of the formal proof (using the proof assistant Coq) of refinement correctness for symmetric nets, a subclass of coloured Petri nets. We provide a formalisation of the net models, and of their type refinement in Coq. Then the Coq proof assistant is used to prove the refinement correctness lemma. An example adapted from a protocol example illustrates our work.     

Checking the reliability of socket based communication software

Locating potential execution errors in software is gaining more attention due to the economical and social impact of software crashes. For this reason, many software engineers are now in need of automatic debugging tools in their development environments. Fortunately, the work on formal method technologies during the past 25 years has produced a number of techniques and tools that can make the debugging task almost automatic, using standard computer equipment and with a reasonable response time. In particular, verification techniques like model-checking that were traditionally employed for formal specifications of the software can now be directly employed for real source code. Due to the maturity of model-checking technology, its application to real software is now a promising and realistic approach to increase software quality. There are already some successful examples of tools for this purpose that mainly work with self-contained programs (programs with no system-calls). However, verifying software that uses external functionality provided by the operating system via API s is currently a challenging trend. In this paper, we propose a method for using the tool spin to verify C software systems that use services provided by the operating system thorough a given API. Our approach consists in building a model of the underlying operating system to be joined with the original C code in order to obtain the input for the model checker spin. The whole modeling process is transparent for the C programmer, because it is performed automatically and without special syntactic constraints in the input C code. Regarding verification, we consider optimization techniques suitable for this application domain, and we guarantee that the system only reports potential (non-spurious) errors. We present the applicability of our approach focusing on the verification of distributed software systems that use the API Socket and the network protocol stack TCP/IP for communications. In order to ensure correctness, we define and use a formal semantics of the API to conduct the construction of correct models.     

Modular specification and verification of object-oriented programs

A method for modular specification and verification using the ideas of subtype and normal type is presented. The method corresponds to informal techniques used by object-oriented programmers. The key idea is that objects of a subtype must behave like objects of that type's supertypes. An example program is used to show the reasoning problems that supertype abstraction may cause and how the method resolves them. Subtype polymorphism is addressed, and specification and verification update is discussed. A set of syntactic and semantic constraints on subtype relationships, which formalize the intuition that each object of a subtype must behave like some object of each of its supertypes, is examined. These constraints are the key to the soundness of the method. To state them precisely, a formal model of abstract type specifications is used     

W-Hierarchies Defined by Symmetric Gates

The classes of the W-hierarchy are the most important classes of intractable problems in parameterized complexity. These classes were originally defined via the weighted satisfiability problem for Boolean circuits. Here, besides the Boolean connectives we consider connectives such as majority, not-all-equal, and unique. For example, a gate labelled by the majority connective outputs true if more than half of its inputs are true. For any finite set C\mathcal{C} of connectives we construct the corresponding W( C\mathcal{C} )-hierarchy. We derive some general conditions which guarantee that the W-hierarchy and the W( C\mathcal{C} )-hierarchy coincide levelwise. If C\mathcal{C} only contains the majority connective then the first levels of the hierarchies coincide. We use this to show that a variant of the parameterized vertex cover problem, the majority vertex cover problem, is W[1]-complete.     

Distributed Mining of Classification Rules

Many successful data-mining techniques and systems have been developed. These techniques usually apply to centralized databases with less restricted requirements on learning and response time. Not so much effort has yet been put into mining distributed databases and real-time issues. In this paper, we investigate issues of fast-distributed data mining. We assume that merging the distributed databases into a single one would either be too costly (distributed case) or the individual fragments would be non-uniform so that mining only one fragment would bias the result (fragmented case). The goal is to classify the objects O of the database into one of several mutually exclusive classes C _i . Our approach to make mining fast and feasible is as follows. From each data site or fragment db _k , only a single rule r _ik is generated for each class C _i . A small subset {r _i1 , …, r _ih } of these individual rules is selected to form a rule set R _i for each class C _i . These rule subsets represent adequately the hidden knowledge of the entire database. Various selection criteria to form R _i are discussed, both theoretically and experimentally. Received 2 February 1999 / Revised 14 July 2000 / Accepted in revised form 27 November 2000     

Graph transformations for object-oriented refinement

An object-oriented program consists of a section of class declarations and a main method. The class declaration section represents the structure of an object-oriented program, that is the data, the classes and relations among them. The execution of the main method realizes the application by invoking methods of objects of the classes defined in the class declarations. Class declarations define the general properties of objects and how they collaborate with each other in realizing the application task programmed as the main method. Note that for one class declaration section, different main methods can be programmed for different applications, and this is an important feature of reuse in object-oriented programming. On the other hand, different class declaration sections may support the same applications, but these different class declaration sections can make significant difference with regards to understanding, reuse and maintainability of the applications. With a UML-like modeling language, the class declaration section of a program is represented as a class diagram, and the instances of the class diagram are represented by object diagrams, that form the state space of the program. In this paper, we define a class diagram and its object diagrams as directed labeled graphs, and investigate what changes in the class structure maintain the capability of providing functionalities (or services). We formalize such a structure change by the notion of structure refinement. A structure refinement is a transformation from one graph to another that preserves the capability of providing services, that is, the resulting class graph should be able to provide at least as many, and as good, services (in terms of functional refinement) as the original graph. We then develop a calculus of object-oriented refinement, as an extension to the classical theory of data refinement, in which the refinement rules are classified into four categories according to their natures and uses in object-oriented software design. The soundness of the calculus is proved and the completeness of the refinement rules of each category is established with regard to normal forms defined for object-oriented programs. These completeness results show the power of the simple refinement rules. The normal forms and the completeness results together capture the essence of polymorphism, dynamic method binding and object sharing by references in object-oriented computation.     

Infinite trees in normal form and recursive equations having a unique solution

A system of recursive equations isC-univocal if it has a unique solution modulo the equivalence associated with a classC of interpretations. This concept yields simplified proofs of equivalence of recursive program schemes and correctness criteria for the validity of certain program transformations, provided one has syntactic easily testable conditions forC-univocality.Such conditions are given for equational classes of interpretations. They rest upon another concept: thenormal form of an infinite tree with respect to a tree rewriting system. This concept yields a simplified construction of the Herbrand interpretation of certain equational classes of interpretations.     

Hierarchical Fusion of Multiple Classifiers for Hyperspectral Data Analysis

Many classification problems involve high dimensional inputs and a large number of classes. Multiclassifier fusion approaches to such difficult problems typically centre around smart feature extraction, input resampling methods, or input space partitioning to exploit modular learning. In this paper, we investigate how partitioning of the output space (i.e. the set of class labels) can be exploited in a multiclassifier fusion framework to simplify such problems and to yield better solutions. Specifically, we introduce a hierarchical technique to recursively decompose a C-class problem into C_1 two-(meta) class problems. A generalised modular learning framework is used to partition a set of classes into two disjoint groups called meta-classes. The coupled problems of finding a good partition and of searching for a linear feature extractor that best discriminates the resulting two meta-classes are solved simultaneously at each stage of the recursive algorithm. This results in a binary tree whose leaf nodes represent the original C classes. The proposed hierarchical multiclassifier framework is particularly effective for difficult classification problems involving a moderately large number of classes. The proposed method is illustrated on a problem related to classification of landcover using hyperspectral data: a 12-class AVIRIS subset with 180 bands. For this problem, the classification accuracies obtained were superior to most other techniques developed for hyperspectral classification. Moreover, the class hierarchies that were automatically discovered conformed very well with human domain experts’ opinions, which demonstrates the potential of using such a modular learning approach for discovering domain knowledge automatically from data. Received: 21 November 2000, Received in revised form: 02 November 2001, Accepted: 13 December 2001     

M<Emphasis Type="SmallCaps">l-rbf</Emphasis>: RBF Neural Networks for Multi-Label Learning

Multi-label learning deals with the problem where each instance is associated with multiple labels simultaneously. The task of this learning paradigm is to predict the label set for each unseen instance, through analyzing training instances with known label sets. In this paper, a neural network based multi-label learning algorithm named Ml-rbf is proposed, which is derived from the traditional radial basis function (RBF) methods. Briefly, the first layer of an Ml-rbf neural network is formed by conducting clustering analysis on instances of each possible class, where the centroid of each clustered groups is regarded as the prototype vector of a basis function. After that, second layer weights of the Ml-rbf neural network are learned by minimizing a sum-of-squares error function. Specifically, information encoded in the prototype vectors corresponding to all classes are fully exploited to optimize the weights corresponding to each specific class. Experiments on three real-world multi-label data sets show that Ml-rbf achieves highly competitive performance to other well-established multi-label learning algorithms.     

Performance analysis of probabilistic action systems

Formal notations like B or action systems support a notion of refinement. Refinement relates an abstract specification A to a concrete specification C that is as least as deterministic. Knowing A and C one proves that C refines, or implements, specification A. In this study we consider specification A as given and concern ourselves with a way to find a good candidate for implementation C. To this end we classify all implementations of an abstract specification according to their performance. We distinguish performance from correctness. Concrete systems that do not meet the abstract specification correctly are excluded. Only the remaining correct implementations C are considered with respect to their performance. A good implementation of a specification is identified by having some optimal behaviour in common with it. In other words, a good refinement corresponds to a reduction of non-optimal behaviour. This also means that the abstract specification sets a boundary for the performance of any implementation. We introduce the probabilistic action system formalism which combines refinement with performance. In our current study we measure performance in terms of long-run expected average-cost. Performance is expressed by means of probability and expected costs. Probability is needed to express uncertainty present in physical environments. Expected costs express physical or abstract quantities that describe a system. They encode the performance objective. The behaviour of probabilistic action systems is described by traces of expected costs. A corresponding notion of refinement and simulation-based proof rules are introduced. Probabilistic action systems are based on discrete-time Markov decision processes. Numerical methods solving the optimisation problems posed by Markov decision processes are well-known, and used in a software tool that we have developed. The tool computes an optimal behaviour of a specification A thus assisting in the search for a good implementation C.Received September 2002 Accepted in revised form January 2004 by E.C.R. Hehner     

Coalgebraic Description of Generalized Binary Methods

We extend the Reichel-Jacobs coalgebraic account of specification and refinement of objects and classes in Object Oriented Programming to (generalized) binary methods. These are methods that take more than one parameter of a class type. Class types include sums and (possibly infinite) products type constructors. We study and compare two solutions for modeling generalized binary methods, which use purely covariant functors. In the first solution, which applies when we already have a class implementation, we reduce the behaviour of a generalized binary method to that of a bunch of unary methods. These are obtained by freezing the types of the extra class parameters to constant types. The bisimulation behavioural equivalence induced on objects by this model amounts to the greatest congruence w.r.t method application. Alternatively, we treat binary methods as graphs instead of functions, thus turning contravariant occurrences in the functor into covariant ones.     

Heuristics for the strip packing problem with unloading constraints

This article addresses the Strip Packing Problem with Unloading Constraints (SPU). In this problem, we are given a strip of fixed width and unbounded height, and n items of C different classes. As in the well-known two-dimensional Strip Packing problem, we have to pack all items minimizing the used height, but now we have the additional constraint that items of higher classes cannot block the way out of lower classes items. This problem appears as a sub-problem in the Two-Dimensional Loading Capacitated Vehicle Routing Problem (2L-CVRP), where one has to optimize the delivery of goods, demanded by a set of clients, that are transported by a fleet of vehicles of limited capacity based at a central depot. We propose two approximation algorithms and a GRASP heuristic for the SPU problem and provide an extensive computational experiment with these algorithms using well know instances for the 2L-CVRP problem as well as new instances adapted from the Strip Packing problem.     

Automating the refinement of specifications for distributed systems via syntactic transformations

The idea of successively refining an abstract specification until it contains enough detail to suggest an implementation has been investigated by numerous researchers. The emphasis to date has been on techniques that, unfortunately, lead to a large amount of manual formal labour for each refinement step. With such techniques, both the cost and the possibility of errors arising informal manipulation are high. Using a theorem prover can reduce the number of manipulation errors, but, given current technology, the amount of labour is still daunting. This research explores an alternative solution to the refinement problem, namely the use of syntactic transformations to realize each refinement step. We reduce formal labour by employing automatic transformations that guarantee the preservation of desirable properties—e.g., deadlock-freedom. Automatic transformations are particularly appealing for the development of large, complex distributed systems, where a manual approach to refinement would be prohibitively expensive. Distributed computations are, by nature, reactive and concurrent, so their correctness cannot be specified as a simple functional relationship between inputs and outputs. Instead, specifications must describe the time-varying behaviour of the system. Further difficulty is caused by the fact that such important characteristics of distributed systems as deadlock-freedom are global properties that cannot be achieved through considering local structures only. Transformations generally must encompass the entire system. This paper presents two syntactic transformations—the left-sequence introduction and the right-sequence introduction—and demonstrates that they preserve deadlock-freedom.     

Application invariants: Design by Contract augmented with deployment correctness logic

Design by Contract is a method for the development of robust object‐oriented software, introducing class invariants as conditions corresponding to the design axioms that should be satisfied by every valid instance of a class. Additionally, the method states formally the way client programs should correctly utilize supplier classes, so that the composition of correct programs may be accomplished. However, the contextual correctness of supplier instances within client programs, only reflected in the client‐specific semantics for supplier‐class deployment, cannot be expressed through Design by Contract. For instance, supplier instances satisfying the supplier class invariant may not constitute plausible supplier instances in the context of a particular client program. In this context, we introduce application invariants as an extension to Design by Contract, for hosting the contextual‐correctness logic for supplier instances, as conditionally defined by client programs. This allows stronger validation of supplier instances, through the dynamic encapsulation of client‐specific acceptance filtering, enabling more intensive defect detection. Application invariants are implemented in the context of client classes as methods utilizing correctness condition expressions, are dynamically hosted within supplier instances, while always called by supplier instances when the basic supplier‐class invariant test is performed. Copyright © 2005 John Wiley & Sons, Ltd.     

A fully abstract semantics of classes for Object-Z

This paper presents a fully abstract semantics of classes for the object oriented formal specification language Object-Z. Such a semantics includes no unnecessary syntactic details and, hence, describes a class in terms of the external behaviour of its objects only. The semantics, based on an extension of existing process models, defines a notion of behavioural equivalence which is stronger than that of CSP and weaker than that of CCS.     

Deriving Proof Rules from Continuation Semantics

We claim that a continuation style semantics of a programming language can provide a starting point for constructing its proof system. The basic idea is to see weakest preconditions as a particular instance of continuation style semantics, hence to interpret correctness assertions (e.g. Hoare triples {p} C {r}) as inequalities over continuations. This approach also shows a correspondence between labels in a program and annotations. Received July 1997 / Accepted in revised form August 1999     

A simple characterization of uniform boundedness for a class of recursions

Detecting bounded recursions is a powerful optimization technique for recursive database query languages, as bounded recursions can be replaced by equivalent nonrecursive definitions. The problem is also of theoretical interest in that varying the class of recursions considered generates problem instances that vary from linearly decidable to NP-hard to undecidable. In this paper we review and clarify the existing definitions of boundedness. We then specify a class of recursions C such that membership in C guarantees that a certain simple condition is necessary and sufficient for boundedness. We use the notion of membership in C to unify and extend previous work on determining decidable classes of bounded recursions.     

The living in a lattice rule language

This paper presents a rule-based query language for an object-oriented database model. The database model supports complex objects, object identity, classes and types, and a class/type hierarchy. The instances are described by ‘object relations’ which are functions from a set of objects to value sets and other object sets. The rule language is based on object-terms which provide access to objects via the class hierarchy. Rules are divided into two classes: object-preserving rules manipulating existing objects (yielding a new ‘view’ on objects available in the object base) and object-generating rules creating new objects with properties derived from existing objects. The derived object sets are included in a class lattice. We give conditions for whether the instances of the ‘rules’ heads are ‘consistent’, i.e. represent object relations where the properties of the derived objects are functionally determined by the objects.