On the (Non-)Existence of Polynomial Kernels for P l -Free Edge Modification Problems

Given a graph G=(V,E) and a positive integer k, an edge modification problem for a graph property Π consists in deciding whether there exists a set F of pairs of V of size at most k such that the graph $H=(V,E\vartriangle F)$ satisfies the property Π. In the Π edge-completion problem, the set F is constrained to be disjoint from E; in the Π edge-deletion problem, F is a subset of E; no constraint is imposed on F in the Π edge-editing problem. A number of optimization problems can be expressed in terms of graph modification problems which have been extensively studied in the context of parameterized complexity (Cai in Inf. Process. Lett. 58:171–176, 1996; Fellows et al. in FCT, pp. 312–321, 2007; Heggernes et al. in STOC, pp. 374–381, 2007). When parameterized by the size k of the set F, it has been proved that if Π is a hereditary property characterized by a finite set of forbidden induced subgraphs, then the three Π edge-modification problems are FPT (Cai in Inf. Process. Lett. 58:171–176, 1996). It was then natural to ask (Bodlaender et al. in IWPEC, 2006) whether these problems also admit a polynomial kernel. in polynomial time to an equivalent instance (G′,k′) with size bounded by a polynomial in k). Using recent lower bound techniques, Kratsch and Wahlström answered this question negatively (Kratsch and Wahlström in IWPEC, pp. 264–275, 2009). However, the problem remains open on many natural graph classes characterized by forbidden induced subgraphs. question to characterize for which type of graph properties, the parameterized edge-modification problems have polynomial kernels. Kratsch and Wahlström asked whether the result holds when the forbidden subgraphs are paths or cycles and pointed out that the problem is already open in the case of P ₄-free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that Parameterized cograph edge-modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for the P _l -free edge-deletion and the C _l -free edge-deletion problems for l?7 and l≥4 respectively. Indeed, if they exist, then NP?coNP/poly.     

Three-stage hybrid-flowshop model for cross-docking

This paper deals with the optimization of a cross-docking system. It is modeled as a three-stage hybrid flowshop, in which shipments and orders are represented as batches. The first stage corresponds to the receiving docks, the second stage corresponds to the sorting stations, and the third stage corresponds to the shipping docks. The objective of the problem is to find a schedule that minimizes the completion time of the latest batch. In order to obtain good quality feasible solutions, we have developed several heuristic schemes depending on the main stage considered, and several rules to order the batches in this stage. Then, we propose a branch-and-bound algorithm that takes into account the decomposition of the problem into three stages. To evaluate the heuristics and to reduce the tree size during the branch-and-bound computation, we also propose lower bounds. Finally, the computational experiments are presented to demonstrate the efficiency of our heuristics. The results show that the exact approach can solve instances containing up to 9–10 batches in each stage (i.e., up to 100 jobs). In addition, our heuristics were evaluated over instances with up to 3000 jobs, and they can provide good quality feasible solutions in a few seconds (i.e., less than 2 s per heuristic).     

THE QSM ALGORITHM AND ITS APPLICATION TO SOFTWARE BEHAVIOR MODEL INDUCTION

This article presents a novel application of grammatical inference techniques to the synthesis of behavior models of software systems. This synthesis is used for the elicitation of software requirements. This problem is formulated as a deterministic finite-state automaton induction problem from positive and negative scenarios provided by an end user of the software-to-be. A query-driven state merging (QSM) algorithm is proposed. It extends the Regular Positive and Negative Inference (RPNI) and blue-fringe algorithms by allowing membership queries to be submitted to the end user. State merging operations can be further constrained by some prior domain knowledge formulated as fluents, goals, domain properties, and models of external software components. The incorporation of domain knowledge both reduces the number of queries and guarantees that the induced model is consistent with such knowledge. The proposed techniques are implemented in the ISIS tool and practical evaluations on standard requirements engineering test cases and synthetic data illustrate the interest of this approach.     

Trust-based security for the OLSR routing protocol

The trust is always present implicitly in the protocols based on cooperation, in particular, between the entities involved in routing operations in Ad hoc networks. Indeed, as the wireless range of such nodes is limited, the nodes mutually cooperate with their neighbors in order to extend the remote nodes and the entire network. In our work, we are interested by trust as security solution for OLSR protocol. This approach fits particularly with characteristics of ad hoc networks. Moreover, the explicit trust management allows entities to reason with and about trust, and to take decisions regarding other entities.In this paper, we detail the techniques and the contributions in trust-based security in OLSR. We present trust-based analysis of the OLSR protocol using trust specification language, and we show how trust-based reasoning can allow each node to evaluate the behavior of the other nodes. After the detection of misbehaving nodes, we propose solutions of prevention and countermeasures to resolve the situations of inconsistency, and counter the malicious nodes. We demonstrate the effectiveness of our solution taking different simulated attacks scenarios. Our approach brings few modifications and is still compatible with the bare OLSR.     

Convex inner approximations of nonconvex semialgebraic sets applied to fixed-order controller design

We describe an elementary algorithm to build convex inner approximations of nonconvex sets. Both input and output sets are basic semialgebraic sets given as lists of defining multivariate polynomials. Even though no optimality guarantees can be given (e.g. in terms of volume maximisation for bounded sets), the algorithm is designed to preserve convex boundaries as much as possible, while removing regions with concave boundaries. In particular, the algorithm leaves invariant a given convex set. The algorithm is based on Gloptipoly 3, a public-domain Matlab package solving nonconvex polynomial optimisation problems with the help of convex semidefinite programming (optimisation over linear matrix inequalities, or LMIs). We illustrate how the algorithm can be used to design fixed-order controllers for linear systems, following a polynomial approach.     

Surface enrichment of biomimetic apatites with biologically-active ions Mg2+ and Sr2+: A preamble to the activation of bone repair materials

The surface activation of calcium phosphate-based biomaterials for bone repair is an emerging route for improving bone regeneration processes. One way for such activation is through the exchange of surface calcium ions with biologically-active cations such as Mg²⁺ or Sr²⁺. In this work, the interactions of non-carbonated and carbonated nanocrystalline apatites with Mg²⁺ and Sr²⁺ were investigated by means of ion exchange experiments in solution. Langmuir-type isotherms were determined. For both Sr and Mg, a greater uptake was observed on the carbonated sample, and on both types of apatites the maximum strontium uptake was greater than that of magnesium. Inverse exchanges showed that the proportion of reversibly fixed ions after surface exchange was close to 85% for Mg and 75–80% for Sr. The results are related to the presence of a surface hydrated layer on the nanocrystals and possible exchange mechanisms are discussed. Our results favor the hypothesis of hetero-ionic surface exchanges (Mg²⁺↔Ca²⁺, Sr²⁺↔Ca²⁺) within the hydrated layer, and some analogy with octacalcium phosphate (OCP) is considered. This work should prove helpful for the control and understanding of the activation of synthetic apatite-based powders or scaffolds with bioactive elements, as well as for the global understanding of biomineralization processes.     

简单MicroBlaze微控制器的理念

MicroBlaze是一款基于构造的的嵌入式微处理器，它的显著优势在于能满足复杂应用的需求，在除了运行简单的通用应用以外，还能运行操作系统。     

Finite element modelling of passive damping with resistively shunted piezocomposites

This work aims at modelling passive damping in structures made of composites with embedded resistively shunted piezoelectric ceramic fibres. To this end, a 3D material model is implemented in the finite element (FE) code ABAQUS. Academical test cases as well as a structural case study are presented.     

Design of dedicated seven-port star dividers for sectored circular antenna array feeding

In order to mitigate the multipath propagation problems for high rate wlans such as Hiperlan (5 GHz) [2], we study an approach based on electronic beam steering over 360° in azimuth with the help of circular arrays of monopoles [3]. Design simplicity and size constraints intended for potential low-cost applications on the terminals has led us to favor a beam switching topology, using a single feeding-port [4]. Two competing configurations of the microstrip feeding circuit are presented and their principle of operation is experimentally validated through passive circuit configurations. The power distribution is achieved in the first one with the help of a pseudo-divider based on a modified 7-branch star junction, whose specific advantage is its very small size. Unfortunately, this design does not preserve the circular permutation invariance of the radiation patterns. The second circuit bypasses this problem in achieving a power distribution through a virtual point junction, at the cost of an appreciable increase in the circuit size.     

Overview of the MPEG Reconfigurable Video Coding Framework

Video coding technology in the last 20 years has evolved producing a variety of different and complex algorithms and coding standards. So far the specification of such standards, and of the algorithms that build them, has been done case by case providing monolithic textual and reference software specifications in different forms and programming languages. However, very little attention has been given to provide a specification formalism that explicitly presents common components between standards, and the incremental modifications of such monolithic standards. The MPEG Reconfigurable Video Coding (RVC) framework is a new ISO standard currently under its final stage of standardization, aiming at providing video codec specifications at the level of library components instead of monolithic algorithms. The new concept is to be able to specify a decoder of an existing standard or a completely new configuration that may better satisfy application-specific constraints by selecting standard components from a library of standard coding algorithms. The possibility of dynamic configuration and reconfiguration of codecs also requires new methodologies and new tools for describing the new bitstream syntaxes and the parsers of such new codecs. The RVC framework is based on the usage of a new actor/ dataflow oriented language called CAL for the specification of the standard library and instantiation of the RVC decoder model. This language has been specifically designed for modeling complex signal processing systems. CAL dataflow models expose the intrinsic concurrency of the algorithms by employing the notions of actor programming and dataflow. The paper gives an overview of the concepts and technologies building the standard RVC framework and the non standard tools supporting the RVC model from the instantiation and simulation of the CAL model to software and/or hardware code synthesis.