Using genetic algorithms to generate test sequences for complex timed systems

The generation of test data for state-based specifications is a computationally expensive process. This problem is magnified if we consider that time constraints have to be taken into account to govern the transitions of the studied system. The main goal of this paper is to introduce a complete methodology, supported by tools, that addresses this issue by representing the test data generation problem as an optimization problem. We use heuristics to generate test cases. In order to assess the suitability of our approach we consider two different case studies: a communication protocol and the scientific application BIPS3D. We give details concerning how the test case generation problem can be presented as a search problem and automated. Genetic algorithms (GAs) and random search are used to generate test data and evaluate the approach. GAs outperform random search and seem to scale well as the problem size increases. It is worth to mention that we use a very simple fitness function that can be easily adapted to be used with other evolutionary search techniques.     

An advanced certificate validation service and architecture based on XKMS

The appearance of some laws that make the electronic signature (e‐signature) legally equivalent to the handwritten signature (under some circumstances) has favoured its use in different fields, such as e‐commerce and e‐government. In these fields, the e‐signatures associated to some documents have to remain valid over long periods of time. For these kinds of e‐signatures, Advanced Electronic Signature (AdES) forms have appeared. These forms specify the information to include along with the e‐signature so that it remains valid for a long time after its creation. Basically, this information comprises signers' certificates, a set of certificates up to a trust anchor, certificate validation responses, etc. These data can be gathered by using different Public Key Infrastructure‐compliant protocols. However, the support of different protocols is complex for clients. XML Key Management Specification (XKMS) appeared with the aim of simplifying the certificate management, but it only supports a simple validation mechanism that does not provide the information needed for long‐term validation. As a solution to this problem, we have extended XKMS by defining an advanced certificate validation service to support the obtaining of validation data needed for different scenarios, such as the building of AdES forms or validation data registries. This extension also defines the different components needed to support this kind of a service. Furthermore, the defined service has been implemented and incorporated into an e‐government infrastructure. Copyright © 2010 John Wiley & Sons, Ltd.     

A priori and a posteriori error analyses of a velocity-pseudostress formulation for a class of quasi-Newtonian Stokes flows

In this paper we introduce and analyze new mixed finite element schemes for a class of nonlinear Stokes models arising in quasi-Newtonian fluids. The methods are based on a non-standard mixed approach in which the velocity, the pressure, and the pseudostress are the original unknowns. However, we use the incompressibility condition to eliminate the pressure, and set the velocity gradient as an auxiliary unknown, which yields a twofold saddle point operator equation as the resulting dual-mixed variational formulation. In addition, a suitable augmented version of the latter showing a single saddle point structure is also considered. We apply known results from nonlinear functional analysis to prove that the corresponding continuous and discrete schemes are well-posed. In particular, we show that Raviart–Thomas elements of order k ? 0 for the pseudostress, and piecewise polynomials of degree k for the velocity and its gradient, ensure the well-posedness of the associated Galerkin schemes. Moreover, we prove that any finite element subspace of the square integrable tensors can be employed to approximate the velocity gradient in the case of the augmented formulation. Then, we derive a reliable and efficient residual-based a posteriori error estimator for each scheme. Finally, we provide several numerical results illustrating the good performance of the resulting mixed finite element methods, confirming the theoretical properties of the estimator, and showing the behaviour of the associated adaptive algorithms.     

A fast and robust bulk-loading algorithm for indexing very large digital elevation datasets II. Experimental results

The spatial indexing of eventually all the available topographic information of Earth is a highly valuable tool for different geoscientific application domains. The Shuttle Radar Topography Mission (SRTM) collected and made available to the public one of the world's largest digital elevation models (DEMs). With the aim of providing on easier and faster access to these data by improving their further analysis and processing, we have indexed the SRTM DEM by means of a spatial index based on the kd-tree data structure, called the Q-tree. This paper is the second in a two-part series that includes a thorough performance analysis to validate the bulk-load algorithm efficiency of the Q-tree. We investigate performance measuring elapsed time in different contexts, analyzing disk space usage, testing response time with typical queries, and validating the final index structure balance. In addition, the paper includes performance comparisons with Oracle 11g that helps to understand the real cost of our proposal. Our tests prove that the proposed algorithm outperforms Oracle 11g using around a 9% of the elapsed time, taking six times less storage with more than 96% of page utilization, and getting faster response times to spatial queries issued on 4.5 million points. In addition to this, the behavior of the spatial index has been successfully tested on both an open GIS (VT Builder) and a visualizer tool derived from the previous one.     

Symbolic approximate time-optimal control

There is an increasing demand for controller design techniques capable of addressing the complex requirements of today’s embedded applications. This demand has sparked the interest in symbolic control where lower complexity models of control systems are used to cater for complex specifications given by temporal logics, regular languages, or automata. These specification mechanisms can be regarded as qualitative since they divide the trajectories of the plant into bad trajectories (those that need to be avoided) and good trajectories. However, many applications require also the optimization of quantitative measures of the trajectories retained by the controller, as specified by a cost or utility function. As a first step towards the synthesis of controllers reconciling both qualitative and quantitative specifications, we investigate in this paper the use of symbolic models for time-optimal controller synthesis. We consider systems related by approximate (alternating) simulation relations and show how such relations enable the transfer of time-optimality information between the systems. We then use this insight to synthesize approximately time-optimal controllers for a control system by working with a lower complexity symbolic model. The resulting approximately time-optimal controllers are equipped with upper and lower bounds for the time to reach a target, describing the quality of the controller. The results described in this paper were implemented in the Matlab Toolbox Pessoa (Mazo et al., 2009 [12]) which we used to workout several illustrative examples reported in this paper.     

An empirical analysis of ontology-based query expansion for learning resource searches using MERLOT and the Gene ontology

This paper proposes an expansion of queries based on formal domain ontologies in the context of the search for learning resources in repositories. The expansion process uses the relation types that are represented in these models; common ontological relations, and ontological relations specific to domain and traditional terminology relations, typical of thesauri. The tests were conducted using Gene ontology as the knowledge base and MERLOT is used as the test repository. The results of this study case indicate that, at similar levels of precision, expanded queries improve levels of novelty and coverage compared to the original query (without expansion), i.e. expanded queries allow the user to retrieve relevant objects, which might not be obtained without expansion.     

Timing and liveness in continuous Petri nets

Fluidification constitutes a relaxation technique for studying discrete event systems through fluidified approximated models, thus avoiding the state explosion problem. Moreover, the class of continuous models thus obtained may be interesting in itself. In Petri nets, fluidification leads to the so-called continuous Petri nets, which are technically hybrid models. Under infinite server semantics, timing a continuous Petri net model preserves the liveness property, but the converse is not necessarily true, and if the autonomous net model is not live, the timing may transform it into a live model. In this paper, we investigate the conditions on the firing rates of timed continuous models that make a given continuous system live.     

Enhancing GPU parallelism in nature-inspired algorithms

We present GPU implementations of two different nature-inspired optimization methods for well-known optimization problems. Ant Colony Optimization (ACO) is a two-stage population-based method modelled on the foraging behaviour of ants, while P systems provide a high-level computational modelling framework that combines the structure and dynamic aspects of biological systems (in particular, their parallel and non-deterministic nature). Our methods focus on exploiting data parallelism and memory hierarchy to obtain GPU factor gains surpassing 20x for any of the two stages of the ACO algorithm, and 16x for P systems when compared to sequential versions running on a single-threaded high-end CPU. Additionally, we compare performance between GPU generations to validate hardware enhancements introduced by Nvidia’s Fermi architecture.