A simple model for laser drilling

A simple mathematical model of laser drilling is proposed. Assuming axi-symmetry of the process around the axis of the laser beam, a one-dimensional formulation is obtained after cross-sectional averaging. The novelty of the approach relies on the fact that even after dimension reduction, the shape of the hole can still be described. The model is derived, implemented and validated for drilling using lasers with intensities in the GW/cm² range and microsecond pulses.     

Project scheduling under resource constraints: Application of the cumulative global constraint in a decision support framework

This paper concerns project scheduling under resource constraints. Traditionally, the objective is to find a unique solution that minimizes the project makespan, while respecting the precedence constraints and the resource constraints. This work focuses on developing a model and a decision support framework for industrial application of the cumulative global constraint. For a given project scheduling, the proposed approach allows the generation of different optimal solutions relative to the alternate availability of outsourcing and resources. The objective is to provide a decision-maker an assistance to construct, choose, and define the appropriate scheduling program taking into account the possible capacity resources. The industrial problem under consideration is modeled as a constraint satisfaction problem (CSP). It is implemented under the constraint programming language CHIP V5. The provided solutions determine values for the various variables associated to the tasks realized on each resource, as well as the curves with the profile of the total consumption of resources on time.     

A network approach to the French system of legal codes—part I: analysis of a dense network

We explore one aspect of the structure of a codified legal system at the national level using a new type of representation to understand the strong or weak dependencies between the various fields of law. In Part I of this study, we analyze the graph associated with the network in which each French legal code is a vertex and an edge is produced between two vertices when a code cites another code at least one time. We show that this network distinguishes from many other real networks from a high density, giving it a particular structure that we call concentrated world and that differentiates a national legal system (as considered with a resolution at the code level) from small-world graphs identified in many social networks. Our analysis then shows that a few communities (groups of highly wired vertices) of codes covering large domains of regulation are structuring the whole system. Indeed we mainly find a central group of influent codes, a group of codes related to social issues and a group of codes dealing with territories and natural resources. The study of this codified legal system is also of interest in the field of the analysis of real networks. In particular we examine the impact of the high density on the structural characteristics of the graph and on the ways communities are searched for. Finally we provide an original visualization of this graph on an hemicyle-like plot, this representation being based on a statistical reduction of dissimilarity measures between vertices. In Part II (a following paper) we show how the consideration of the weights attributed to each edge in the network in proportion to the number of citations between two vertices (codes) allows deepening the analysis of the French legal system.     

Nondeterministic Graph Searching: From Pathwidth to Treewidth

We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called q -branched tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of q-branched tree decompositions. The equivalence between nondeterministic graph searching and q-branched tree decomposition enables us to design an exact (exponential time) algorithm computing q-branched treewidth for all q≥0, which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers. Additional support of F.V. Fomin by the Research Council of Norway. Additional supports of P. Fraigniaud from the INRIA Project “Grand Large”, and from the Project PairAPair of the ACI “Masse de Données”. Additional supports of N. Nisse from the Project Fragile of the ACI “Sécurité & Informatique”.     

Labeling Schemes for Tree Representation

This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling ℒ _all gives each node v of G a label containing the port numbers of all the tree edges incident to v. The upward tree labeling ℒ _up labels each node v by the number of the port leading from v to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted M _up (T) and S _up (T) for ℒ _up and M _all (T) and S _all (T) for ℒ _all . The problem studied in this paper is the following: Given a graph G and a predefined port labeling for it, with the ports of each node v numbered by 0,…,deg (v)−1, select a rooted spanning tree for G minimizing (one of) these measures. We show that the problem is polynomial for M _up (T), S _up (T) and S _all (T) but NP-hard for M _all (T) (even for 3-regular planar graphs). We show that for every graph G and port labeling there exists a spanning tree T for which S _up (T)=O(nlog log n). We give a tight bound of O(n) in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port labeling. We conclude by discussing some applications for our tree representation schemes. A preliminary version of this paper has appeared in the proceedings of the 7th International Workshop on Distributed Computing (IWDC), Kharagpur, India, December 27–30, 2005, as part of Cohen, R. et al.: Labeling schemes for tree representation. In: Proceedings of 7th International Workshop on Distributed Computing (IWDC), Lecture Notes of Computer Science, vol. 3741, pp. 13–24 (2005). R. Cohen supported by the Pacific Theaters Foundation. P. Fraigniaud and D. Ilcinkas supported by the project “PairAPair” of the ACI Masses de Données, the project “Fragile” of the ACI Sécurité et Informatique, and by the project “Grand Large” of INRIA. A. Korman supported in part by an Aly Kaufman fellowship. D. Peleg supported in part by a grant from the Israel Science Foundation.     

Assessment of Digital Elevation Model (DEM) aggregation methods for hydrological modeling: Lake Chad basin,Africa

Digital Elevation Models (DEMs) are used to compute the hydro-geomorphological variables required by distributed hydrological models. However, the resolution of the most precise DEMs is too fine to run these models over regional watersheds. DEMs therefore need to be aggregated to coarser resolutions, affecting both the representation of the land surface and the hydrological simulations. In the present paper, six algorithms (mean, median, mode, nearest neighbour, maximum and minimum) are used to aggregate the Shuttle Radar Topography Mission (SRTM) DEM from 3″ (90 m) to 5′ (10 km) in order to simulate the water balance of the Lake Chad basin (2.5 Mkm²). Each of these methods is assessed with respect to selected hydro-geomorphological properties that influence Terrestrial Hydrology Model with Biogeochemistry (THMB) simulations, namely the drainage network, the Lake Chad bottom topography and the floodplain extent.The results show that mean and median methods produce a smoother representation of the topography. This smoothing involves the removing of the depressions governing the floodplain dynamics (floodplain area<5000 km²) but it eliminates the spikes and wells responsible for deviations regarding the drainage network. By contrast, using other aggregation methods, a rougher relief representation enables the simulation of a higher floodplain area (>14,000 km² with the maximum or nearest neighbour) but results in anomalies concerning the drainage network. An aggregation procedure based on a variographic analysis of the SRTM data is therefore suggested. This consists of preliminary filtering of the 3″ DEM in order to smooth spikes and wells, then resampling to 5′ via the nearest neighbour method so as to preserve the representation of depressions. With the resulting DEM, the drainage network, the Lake Chad bathymetric curves and the simulated floodplain hydrology are consistent with the observations (3% underestimation for simulated evaporation volumes).     

Action Recognition Using a Bio-Inspired Feedforward Spiking Network

We propose a bio-inspired feedforward spiking network modeling two brain areas dedicated to motion (V1 and MT), and we show how the spiking output can be exploited in a computer vision application: action recognition. In order to analyze spike trains, we consider two characteristics of the neural code: mean firing rate of each neuron and synchrony between neurons. Interestingly, we show that they carry some relevant information for the action recognition application. We compare our results to Jhuang et al. (Proceedings of the 11th international conference on computer vision, pp. 1–8, 2007) on the Weizmann database. As a conclusion, we are convinced that spiking networks represent a powerful alternative framework for real vision applications that will benefit from recent advances in computational neuroscience.     

Investigating the usability of real-time scheduling theory with the Cheddar project

This article deals with real-time critical systems modelling and verification. Real-time scheduling theory provides algebraic methods and algorithms in order to make timing constraints verifications of these systems. Nevertheless, many industrial projects do not perform analysis with real-time scheduling theory even if demand for use of this theory is large and the industrial application field is wide (avionics, aerospace, automotive, autonomous systems, …). The Cheddar project investigates why real-time scheduling theory is not used and how its usability can be increased. The project was launched at the University of Brest in 2002. In Lecture Notes on Computer Sciences, vol. 5026, pp. 240–253, 2008, we have presented a short overview of this project. This article is an extended presentation of the Cheddar project, its contributions and also its ongoing works.     

Using online simulation in Holonic manufacturing systems

This paper deals with the use of online simulation on Holonic manufacturing systems. Concepts needed for the use of online simulation in a classical hierarchical system were already defined, the observer being the central one. The behavior's differences between both classes of systems are studied to determine the best way to adapt these concepts to this new environment. In the product resource order staff approach (PROSA) reference architecture, staff holons were chosen to welcome the simulation models and the observer. An application on an industrial sized Holonic manufacturing system is described to demonstrate the validity of the approach.     

Formal Proofs of Rounding Error Bounds

Floating-point arithmetic is a very efficient solution to perform computations in the real field. However, it induces rounding errors making results computed in floating-point differ from what would be computed with reals. Although numerical analysis gives tools to bound such differences, the proofs involved can be painful, hence error prone. We thus investigate the ability of a proof assistant like Coq to mechanically check such proofs. We demonstrate two different results involving matrices, which are pervasive among numerical algorithms, and show that a large part of the development effort can be shared between them.