Search

27 pages, International audience, This paper presents an experience report on the specification and the validation of a real case study in the context of the industrial CRISTAL project. The case study concerns a platoon of a new type of urban vehicles with new functionalities and services. It is specified using the combination, named CSP$\|$B, of two well-known formal methods, and validated using the corresponding support tools. This large -- both distributed and embedded -- system typically corresponds to a multi-level composition of components that have to cooperate. We identify some lessons learned, showing how to develop and verify the specification and check some properties in a compositional way using theoretical results and support tools to validate this complex system.

International audience, Recently, several studies taking into account the ability for a gene to be absent or to have some copies in genomes have been proposed, as the examplar distance [11, 6] or the gene matching computation between two genomes [10, 3]. In this paper, we study the time complexity of the conserved interval distance computation considering duplicated genes using both those two strategies.

International audience, The longest common subsequence (LCS) problem is a classic and well-studied problem in computer science with extensive applications in diverse areas ranging from spelling error corrections to molecular biology. This paper focuses on LCS for fixed alphabet size and fixed run-lengths (i.e., maximum number of consecutive occurrences of the same symbol). We show that LCS is NP-complete even when restricted to (i) alphabets of size 3 and run-length at most 1, and (ii) alphabets of size 2 and run-length at most 2 (both results are tight). For the latter case, we show that the problem is approximable within ratio 3/5.

International audience, Domains in Continuous Constraint Programming (CP) are generally represented with intervals whose $n$-ary Cartesian product (box) approximates the solution space. This paper proposes a new representation for continuous variable domains based on octagons. We generalize local consistency and split to this octagon representation, and we propose an octagonal-based branch and prune algorithm. Preliminary experimental results show promising performance improvements on several classical benchmarks.

ISBN: 3-540-23095-5, In this paper, we present a tool for estimating the activity of asynchronous circuit specifications. This tool is well suited for monitoring how and where the activity is spread in a circuit. The quality and the precision of the results allow the designer to perform optimizations early in the design flow in order to improve the energy consumption and the speed of asynchronous circuits. Based on the TAST profiler, an energy optimization methodology is defined, focusing on micro-architecture decomposition, choice structures unbalancing and channels splitting. All these techniques are illustrated using an example.

International audience, Given two arc-annotated sequences (S, P ) and (T, Q) representing RNA structures, the Arc-Preserving Subsequence (APS) problem asks whether (T, Q) can be obtained from (S, P ) by deleting some of its bases (together with their incident arcs, if any). In previous studies [3, 6], this problem has been naturally divided into subproblems reflecting intrinsic complexity of arc structures. We show that APS(Crossing, Plain) is NP-complete, thereby answering an open problem [6]. Furthermore, to get more insight into where actual border of APS hardness is, we refine APS classical subproblems in much the same way as in [11] and give a complete categorization among various restrictions of APS problem complexity.

International audience, We study the problem of phylogenetic reconstruction based on gene order for whole genomes. We define three genomic distances between whole genomes represented by signed sequences, based on the matching of similar segments of genes and on the notions of breakpoints, conserved intervals and common intervals. We use these distances and distance based phylogenetic reconstruction methods to compute a phy- logeny for a group of 12 complete genomes of γ-Proteobacteria.