A novel model-based testing approach for software product lines

Model-based testing relies on a model of the system under test. FineFit is a framework for model-based testing of Java programs. In the FineFit approach, the model is expressed by a set of tables based on Parnas tables. A software product line is a family of programs (the products) with well-defined commonalities and variabilities that are developed by (re)using common artifacts. In this paper, we address the issue of using the FineFit approach to support the development of correct software product lines. We specify a software product line as a specification product line where each product is a FineFit specification of the corresponding software product. The main challenge is to concisely specify the software product line while retaining the readability of the specification of a single system. To address this, we used delta-oriented programming, a recently proposed flexible approach for implementing software product lines, and developed: (1) delta tables as a means to apply the delta-oriented programming idea to the specification of software product lines; and (2) DeltaFineFit as a novel model-based testing approach for software product lines.     

Energy-optimal collaborative file distribution in wired networks

The impact of the ICT sector in worldwide power consumption is an increasing concern, motivating the research community to devote an important effort to define novel energy efficient networking solutions. Despite file distribution is responsible for a major portion of the current Internet traffic, little effort has been dedicated to address the issue of its energy efficiency so far. Most of the previous literature focuses on optimizing the download time of file distribution schemes (e.g. centralized server-based or distributed peer-to-peer solutions) while it is yet unclear how to optimize file distribution schemes from the point of view of energy consumed. In this paper, we present a general modelling framework to analyze the energy consumption of file distribution systems. First, we show that the general problem of minimizing energy consumption in file distribution is NP-hard. Then, for restricted versions of the problem, we establish theoretical bounds to minimal energy consumption. Furthermore, we define a set of optimal algorithms for a variety of system settings, which exploit the service capabilities of hosts in a P2P fashion. We show that our schemes are capable of reducing at least 50 % of the energy consumed by traditional (yet largely used) centralized distribution schemes even when considering effects such as network congestion and heterogeneous access speed across nodes.     

The languages FCP(:) and FCP(:,?)

The language FCP(:,?) is the outcome of attempts to integrate the best of several flat concurrent logic programming languages, including Flat GHC, FCP (↓, |) and Flat Concurrent Prolog, in a single consistent framework. FCP(:) is a subset of FCP(:, ?), which is a variant of FPP(↓, |) and employs concepts of the concurrent constraint framework of cc(↓, |). FCP(:, ?) is a language which is strong enough to accommodate all useful concurrent logic programming techniques, including those which rely on atomic test unification and read-only variables, yet incorporates the weaker languages mentioned as subsets. This allows the programmer to remain within a simple subset of the language such as Flat GHC when the full power of atomic unification or read-only variables is not needed.     

A closer look at termination

Summary Several methods for proving that computer programs terminate are presented and illustrated. The methods considered involve (a) using the no-infinitely-descending-chain property of well-founded sets (Floyd's approach), (b) bounding a counter associated with each loop (loop approach), (c) showing that some exit of each loop must be taken (exit approach), or (d) inducting on the structure of the data domain (Burstall's approach). We indicate the relative merit of each method for proving termination or non-termination as an integral part of an automatic verification system.     

A low energy dual-mode adder

VLSI designs are typically data-independent and as such, they must produce the correct result even for the worst-case inputs. Adders in particular assume that addition must be completed within prescribed number of clock cycles, independently of the operands. While the longest carry propagation of an n-bit adder is n bits, its expected length is only O(log₂ n) bits. We present a novel dual-mode adder architecture that reduces the average energy consumption in up to 50%. In normal mode the adder targets the O(log₂ n)-bit average worst-case carry propagation chains, while in extended mode it accommodates the less frequent O(n)-bit chain. We prove that minimum energy is achieved when the adder is designed for O(log₂ n) carry propagation, and present a circuit implementation. Dual-mode adders enable voltage scaling of the entire system, potentially supporting further overall energy reduction. The energy-time tradeoff obtained when incorporating such adders in ordinary microprocessor’s pipeline and other architectures is discussed.     

On the Complexity of the Regenerator Cost Problem in General Networks with Traffic Grooming

In a communication network one often needs to combine several communication requests into a path in a physical layer of the network. In these cases the cost is measured in terms of the total length of these paths or the total hardware cost of maintaining these paths. In this paper we consider a problem belonging to this general family of optimization problems. We consider the problem of minimizing the number of regenerators in optical networks with traffic grooming. In this problem we are given a network with an underlying topology of a graph G, a set of requests that correspond to paths in G and two positive integers g and d. There is a need to put a regenerator every d edges of every path, because of a degradation in the quality of the signal. Each regenerator can be shared by at most g paths, g being the grooming factor. On the one hand, we show that even in the case of d=1 the problem is APX-hard, i.e. a polynomial time approximation scheme for it does not exist (unless P=NP). On the other hand, we solve such a problem for general G and any d and g, by providing an O(logg)-approximation algorithm and thus extending previous results holding only for specific topologies and specific values of d or g.     

Fairness and the axioms of control predicates

Many recent axiomatic definitions for structured programming languages include control predicates,at(S), in(S), andafter(S), which are an abstraction of location counters. The usual axioms identify control locations so as to imply that no time (i.e., no state transition) is needed to pass from the end of one statement to the next, and in particular from the end of a loop body back to the test at the head of the loop. Here, an axiomatic framework for control predicates is examined. It is shown that if all the axioms are to be maintained with common representation mappings, there are difficult new requirements which need to be satisfied by an implementation for fair concurrent models of computation. Several approaches to resolving the difficulty are considered, and in particular it is suggested to replace some axioms of the formPQ byPeventually(Q), whereP andQ are control predicates, thereby separating control states previously identified.The North has receded, but the South has not yet arrived.-Reuven Miran, 42 Degrees in the Shade Every three lines intersect at a point, if the point is thick enough.-Folk theoremNote: A talk based on this paper was presented at the Colloquium on Temporal Logic and Specification, Altrincham, Cheshire, April 1987.C.R. Categories: D.3.1 [Programming languages] Formal definitions and theory: semantics; D..3.3 [Programming languages] Language constructs: control structures; F.3.1. [Logics and meanings of programs] Specifying and verifying and reasoning about programs.     

Compact flashlamp-based fluorescence imager for use under ambient-light conditions

A low-power, lightweight, multiwavelength fluorescence imager based on the use of a compact xenon flashlamp, bandpass filters, gated charge-coupled device camera, and digital image processing was developed for use on an autonomous rover vehicle. The imager discriminates against ambient light by use of microsecond excitation pulses along with synchronized camera operation to limit the time period in which ambient-light photocounts are accumulated, and digital image subtraction to remove background counts. In a 10 cm square field of view, weak fluorescence, equivalent to 0.05 pmol fluorescein/mm(2), can be quantified against a white-light background equivalent to shaded sunlight. For application in autonomous search for organisms in extreme environments such as in situ desert rock or soil, the instrument was equipped with a set of fluorescence excitation filters (380, 450, 545, and 600 nm) and emission filters (460, 510, 620, and 740 nm) suitable for detection of chlorophyll, applied stains for protein, DNA, lipid and carbohydrate, and autofluorescence. True-color images were obtained through red-green-blue imaging filters (630, 535, and 470 nm) used with white-light flashes. Automated focusing on ground features was based on the R-band image and was carried out prior to fluorescence image acquisition.     

Three-part auctions versus self-commitment in day-ahead electricity markets

We examine the economic consequences of a bid-based security-constrained centralized unit commitment paradigm based on three-part offers, which is the prevalent day-ahead market-clearing mechanism in restructured electricity markets in the United States. We then compare this approach with an energy-only auction with self-commitment (such as in Australia) addressing efficiency and pricing as well as the tradeoff between coordination losses and incentives to bid truthfully.     

Analysis of explosives by nuclear magnetic resonance spectrometry

In order to evaluate the applicability of NMR to the analysis of explosives, the method was used to analyse explosives from actual cases. The results were then compared with results from other analytical methods, mainly TLC and GC/MS. For unexploded samples NMR was found to be a simple, fast and reliable method, often allowing the identification of mixtures without pre-separation. Some post-explosion samples were also successfully analysed by NMR. Although sensitivity problems still exist, NMR showed a surprisingly promising prospects for the difficult field of post-explosion analysis.