Well-structured languages

This paper introduces the notion of well-structured language. A well-structured language can be defined by a labelled well-structured transition system, equipped with an upward-closed set of accepting states. That peculiar class of transition systems has been extensively studied in the field of computer-aided verification, where it has direct an important applications. Petri nets, and their monotonic extensions (like Petri nets with non-blocking arcs or Petri nets with transfer arcs), for instance, are special subclasses of well-structured transition systems. We show that the class of well-structured languages enjoy several important closure properties. We propose several pumping lemmata that are applicable respectively to the whole class of well-structured languages and to the classes of languages recognized by Petri nets or Petri nets with non-blocking arcs. These pumping lemmata allow us to characterize the limits in the expressiveness of these classes of language. Furthermore, we exploit the pumping lemmata to strictly separate the expressive power of Petri nets, Petri nets with non-blocking arcs and Petri nets with transfer arcs.     

Hydraulic behaviour of a representative structural volume for containment buildings

For particular structures like containment buildings of nuclear power plants, the study of the hydraulic behaviour is of great concern. These structures are indeed the third barrier used to protect the environment in case of accidents. The evolution of the leaking rate through the porous medium is closely related to the changes in the permeability during the ageing process of the structure. It is thus essential to know the relation between concrete degradation and the transfer property when the consequences of a mechanical loading on the hydraulic behaviour have to be evaluated. A chained approach is designed for this purpose. The mechanical behaviour is described by an elastic plastic damage formulation, where damage is responsible for the softening evolution while plasticity accounts for the development of irreversible strains. The drying process is evaluated according to a non-linear equation of diffusion. From the knowledge of the damage and the degree of saturation, a relation is proposed to calculate the permeability of concrete. Finally, the non-homogeneous distribution of the hydraulic conductivity is included in the hydraulic problem which is in fact the association of the mass balance equation for gas phase and Darcy law. From this methodology, it is shown how an indicator for the hydraulic flows can be deduced.     

Quantum speed-up for unsupervised learning

We show how the quantum paradigm can be used to speed up unsupervised learning algorithms. More precisely, we explain how it is possible to accelerate learning algorithms by quantizing some of their subroutines. Quantization refers to the process that partially or totally converts a classical algorithm to its quantum counterpart in order to improve performance. In particular, we give quantized versions of clustering via minimum spanning tree, divisive clustering and k-medians that are faster than their classical analogues. We also describe a distributed version of k-medians that allows the participants to save on the global communication cost of the protocol compared to the classical version. Finally, we design quantum algorithms for the construction of a neighbourhood graph, outlier detection as well as smart initialization of the cluster centres.     

Multiprocessor schedulability of arbitrary-deadline sporadic tasks: complexity and antichain algorithm

Baker and Cirinei (Lecture Notes in Computer Science, vol. 4878, Springer, pp. 62–75, 2007) have introduced an exact but naive algorithm, that consists in solving a state reachability problem in a finite automaton, to check whether a set of sporadic hard real-time tasks is schedulable on an identical multiprocessor platform. However, this algorithm suffers from poor performance due to the exponential size of the automaton relative to the size of the task set. In this paper, we build on the work of Baker and Cirinei, and rely on their formalism to characterise the complexity of this problem. We prove that it is PSpace-complete. In order to obtain an algorithm that is applicable in practice to systems of realistic sizes, we successfully apply techniques developed by the formal verification community, specifically antichain techniques (Doyen and Raskin in Lecture Notes in Computer Science, vol. 6015, Springer, pp. 2–22, 2010) to this scheduling problem. For that purpose, we define and prove the correctness of a simulation relation on Baker and Cirinei’s automaton. We show that our improved algorithm yields dramatically improved performance for the schedulability test and opens for many further improvements. This work is an extended and revised version of a previous conference paper by the same authors (Lindström et al., Proceedings of the 19th International Conference on Real-Time and Network Systems (RTNS 2011), pp. 25–34, 2011).     

Left invertibility,flatness and identifiability of switched linear dynamical systems: a framework for cryptographic applications

The purpose of this article is to illustrate the potential interest of the control theory framework for cryptographic applications. It is shown that under the properties of left invertibility and flatness, dynamical systems are structurally equivalent to some specific cryptographic primitives called self-synchronising stream ciphers. After having motivated the interest of considering hybrid systems for such ciphers, the development is particularised for the special class of switched linear systems. We also show that identifiability is a necessary condition for security, and we describe an identification procedure as a possible attack and assess its complexity.     

The MISTIGRI thermal infrared project: scientific objectives and mission specifications

This article presents the MISTIGRI project of a microsatellite developed by the French space agency Centre National d'Etudes Spatiales (CNES) in cooperation with Spain (Image Processing Laboratory of the University of Valencia and Centro para el Desarrollo Tecnológico Industrial (CDTI)). MISTIGRI is a mission that has the originality of combining a high spatial resolution (～50 m) with a daily revisit in the thermal infrared (TIR). MISTIGRI is an experimental mission devoted to demonstrate the potential of such TIR data for future operational missions. The scientific goals and expected applications of the mission are described: they encompass the monitoring of (i) agricultural areas and related hydrological processes, (ii) urban areas, and (iii) coastal areas and continental waters. Then, the specifications on spatial resolution, revisit frequency, overpass time, and spectral configuration are justified. The strategy of the mission is based on the combination with a network of long-term experimental sites. It will also make possible observing some areas facing rapid climatic change. The choice of the orbit is presented. Finally, we give rapid overviews of both the instrumental concept and the proposed mission architecture.     

Non-linear dynamic system identification: A multi-model approach

We are concerned with models which are able to describe multiple-input multiple-output (MIMO) non-linear dynamic systems. These models are represented in the form of rules and are known as Tagaki-Sugeno models. An identification algorithm for these models based on input and output data is presented. Parameter estimation is based on the calculation of model sensitivity functions with respect to their parameters. Some aspects of structure identification are also tackled, i.e. determination of local model orders and number of rules.     

Region-Based Active Contours with Exponential Family Observations

In this paper, we focus on statistical region-based active contour models where image features (e.g. intensity) are random variables whose distribution belongs to some parametric family (e.g. exponential) rather than confining ourselves to the special Gaussian case. In the framework developed in this paper, we consider the general case of region-based terms involving functions of parametric probability densities, for which the anti-log-likelihood function is a special case. Using shape derivative tools, our effort focuses on constructing a general expression for the derivative of the energy (with respect to a domain), and on deriving the corresponding evolution speed. More precisely, we first show by an example that the estimator of the distribution parameters is crucial for the derived speed expression. On the one hand, when using the maximum likelihood (ML) estimator for these parameters, the evolution speed has a closed-form expression that depends simply on the probability density function. On the other hand, complicating additive terms appear when using other estimators, e.g. method of moments. We then proceed by stating a general result within the framework of multi-parameter exponential family. This result is specialized to the case of the anti-log-likelihood function with the ML estimator and to the case of the relative entropy. Experimental results on simulated data confirm our expectations that using the appropriate noise model leads to the best segmentation performance. We also report preliminary experiments on real life Synthetic Aperture Radar (SAR) images to demonstrate the potential applicability of our approach.     

Assessing the effect of nutrient mitigation measures in the watersheds of the Southern Bight of the North Sea

The Seine, Somme, and Scheldt Rivers (France, Belgium, and Netherlands) are the major delivering rivers flowing into the continental coastal zone of the Southern Bight of the North Sea, an area regularly affected by eutrophication problems. In the present work, the Seneque-Riverstrahler model was implemented in a multi-regional case study in order to test several planned mitigation measures aimed at limiting stream nutrient contamination and restoring balanced nutrient ratios at the coastal zone.This modeling approach, which is spatially distributed at the basin scale, allows assessing the impact of any change in human activities, which widely differ over the three basins. Here, we define realistic scenarios based on currently proposed measures to reduce point and non-point sources, such as the upgrading of wastewater treatment, the introduction of catch crops, and the development of extensive farming. An analysis of the current situation showed that a 47-72% reduction in P point-source emissions within the three basins could be reached if the intended P treatment was generalized to the largest treatment plants. However, only an overall 14-23% reduction in N could be achieved at the outlet of the three basins, by combining improved wastewater treatment and land use with management measures aimed at regulating agricultural practices. Nonetheless, in spite of these efforts, N will still be exported in large excess with respect to the equilibrium defined by the Redfield ratios, even in the most optimistic hypothesis describing the long-term response of groundwater nitrate concentrations.A comprehensive assessment of these mitigation measures supports the need for additional reductions of nutrient losses from agriculture to control harmful algae development. It also stresses the relevance of this mechanistic approach, in which nutrient transfers from land to sea can be calculated, as an integrated strategy to test policy recommendations.