The Failure of the Strong Pumping Lemma for Multiple Context-Free Languages

Seki et al. (Theor. Comput. Sci. 88(2):191–229, 1991) showed that every m-multiple context-free language L is weakly 2m-iterative in the sense that either L is finite or L contains a subset of the form \(\{ u_{0} w_{1}^{i} u_{1} \cdots w_{2m}^{i} u_{2m} \mid i \in \mathbb {N}\}\) , where w ₁?w _2n ≠ε. Whether every m-multiple context-free language L is 2m-iterative, that is to say, whether all but finitely many elements z of L can be written as z=u ₀ w ₁ u ₁?w _2m u _2m with w ₁?w _2m ≠ε and \(\{ u_{0} w_{1}^{i} u_{1} \cdots w_{2m}^{i} u_{2m} \mid i \in \mathbb {N}\} \subseteq L\) , has been open. We show that there is a 3-multiple context-free language that is not k-iterative for any k.     

Measuring and Improving Image Resolution by Adaptation of the Reciprocal Cell

Traditionally, discrete images are assumed to be sampled on a square grid and from a special kind of band-limited continuous image, namely one whose Fourier spectrum is contained within the rectangular reciprocal cell associated with the sampling grid. With such a simplistic model, resolution is just given by the distance between sample points.Whereas this model matches to some extent the characteristics of traditional acquisition systems, it doesn't explain aliasing problems, and it is no longer valid for certain modern ones, where the sensors may show a heavily anisotropic transfer function, and may be located on a non-square (in most cases hexagonal) grid.In this work we first summarize the generalizations of Fourier theory and of Shannon's sampling theorem, that are needed for such acquisition devices. Then we explore its consequences: (i) A new way of measuring the effective resolution of an image acquisition system; (ii) A more accurate way of restoring the original image which is represented by the samples. We show on a series of synthetic and real images, how the proposed methods make a better use of the information present in the samples, since they may drastically reduce the amount of aliasing with respect to traditional methods. Finally we show how in combination with Total Variation minimization, the proposed methods can be used to extrapolate the Fourier spectrum in a reasonable manner, visually increasing image resolution.     

Strategies for combining decision procedures

Implementing efficient algorithms for combining decision procedures has been a challenge and their correctness precarious. In this paper we describe an inference system that has the classical Nelson–Oppen procedure at its core and includes several optimizations: variable abstraction with sharing, canonization of terms at the theory level, and Shostak's streamlined generation of new equalities for theories with solvers. The transitions of our system are fine-grained enough to model most of the mechanisms currently used in designing combination procedures. In particular, with a simple language of regular expressions we are able to describe several combination algorithms as strategies for our inference system, from the basic Nelson–Oppen to the very highly optimized one recently given by Shankar and Rueß. Presenting the basic system at a high level of generality and non-determinism allows transparent correctness proofs that can be extended in a modular fashion when new features are introduced in the system.     

Leaf area index mapping in northern Canada

Leaf area index (LAI) is an important structural vegetation parameter that is commonly derived from remotely sensed data. It has been used as a reliable indicator for vegetation's cover, status, health and productivity. In the past two decades, various Canada-wide LAI maps have been generated by the Canada Centre for Remote Sensing (CCRS). These products have been produced using a variety of very coarse satellite data such as those from SPOT VGT and NOAA AVHRR satellite data. However, in these LAI products, the mapping of the Canadian northern vegetation has not been performed with field LAI measurements due in large part to scarce in situ measurements over northern biomes. The coarse resolution maps have been extensively used in Canada, but finer resolution LAI maps are needed over the northern Canadian ecozones, in particular for studying caribou habitats and feeding grounds.

In this study, a new LAI algorithm was developed with particular emphasis over northern Canada using a much finer resolution of remotely sensed data and in situ measurements collected over a wide range of northern arctic vegetation. A statistical relationship was developed between the in situ LAI measurements collected over vegetation plots in northern Canada and their corresponding pixel spectral information from Landsat Thematic Mapper (TM) and Enhanced Thematic Mapper Plus (ETM+) data. Furthermore, all Landsat TM and ETM+ data have been pre-normalized to NOAA AVHRR and SPOT VGT data from the growing season of 2005 to reduce any seasonal or temporal variations. Various spectral vegetation indices developed from the Landsat TM and ETM?+?data were analysed in this study. The reduced simple ratio index (RSR) was found to be the most robust and an accurate estimator of LAI for northern arctic vegetation. An exponential relationship developed using the Theil–Sen regression technique showed an R ² of 0.51 between field LAI measurement and the RSR. The developed statistical relationship was applied to a pre-existing Landsat TM 250 m resolution mosaic for northern Canada to produce the final LAI map for northern Canada ecological zones. Furthermore, the 250 m resolution LAI estimates, per ecological zone, were almost generally lower than those of the CCRS Canada-wide VGT LAI maps for the same ecozones. Validation of the map with LAI field data from the 2008 season, not used in the derivation of the algorithm, shows strong agreement between the in situ LAI measurement values and the map-estimated LAI values.     

Finding and Counting Vertex-Colored Subtrees

The problems studied in this article originate from the Graph Motif problem introduced by Lacroix et al. (IEEE/ACM Trans. Comput. Biol. Bioinform. 3(4):360–368, 2006) in the context of biological networks. The problem is to decide if a vertex-colored graph has a connected subgraph whose colors equal a given multiset of colors M. It is a graph pattern-matching problem variant, where the structure of the occurrence of the pattern is not of interest but the only requirement is the connectedness. Using an algebraic framework recently introduced by Koutis (Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 5125, pp. 575–586, 2008) and Koutis and Williams (Proceedings of the 36th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science, vol. 5555, pp. 653–664, 2009), we obtain new FPT algorithms for Graph Motif and variants, with improved running times. We also obtain results on the counting versions of this problem, proving that the counting problem is FPT if M is a set, but becomes #W[1]-hard if M is a multiset with two colors. Finally, we present an experimental evaluation of this approach on real datasets, showing that its performance compares favorably with existing software.     

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.     

Energy-aware feedback control for a H.264 video decoder

Embedded devices using highly integrated chips must cope with conflicting constraints, while executing computationally demanding applications under limited energy storage. Automatic control and feedback loops appear to be an effective solution to simultaneously accommodate for performance uncertainties due to the tiny scale gates variability, varying and poorly predictable computing demands and limited energy storage constraints. This paper presents the example of an embedded video decoder controlled by several feedback loops to carry out the trade-off between decoding quality and energy consumption, exploiting the frequency and voltage scaling capabilities of the chip. The inner loop controls the dynamic voltage and frequency scaling through a fast predictive control strategy. The outer loop computes the scheduling set-points needed by the inner loop to process frames decoding. The feedback loops have been implemented on a stock PC and experimental results are provided.     

Model falsification diagnosis and sensor placement for leak detection in pressurized pipe networks

Pressurized pipe networks used for fresh-water distribution can take advantage of recent advances in sensing technologies and data-interpretation to evaluate their performance. In this paper, a leak-detection and a sensor placement methodology are proposed based on leak-scenario falsification. The approach includes modeling and measurement uncertainties during the leak detection process. The performance of the methodology proposed is tested on a full-scale water distribution network using simulated data. Findings indicate that when monitoring the flow velocity for 14 pipes over the entire network (295 pipes) leaks are circumscribed within a few potential locations. The case-study shows that a good detectability is expected for leaks of 50 L/min or more. A study of measurement configurations shows that smaller leak levels could also be detected if additional pipes are instrumented.     

GEAMAS: A Generic Architecture for Agent-Oriented Simulations of Complex Processes

This paper's object is to present the results of the GEAMAS project which aims at modeling and simulating natural complex systems. GEAMAS is a generic architecture of agents used to study the behavior emergence in such systems. It is a multiagent program meant to develop simulation applications. Modeling complex systems requires to reduce, to organize the system complexity and to describe suitable components. Complexity of the system can then be tackled with an agent-oriented approach, where interactions lead to a global behavior. This approach helps in understanding how non-determinist behavior can emerge from interactions between agents, which is near of self-organized criticality used to explain natural phenomena. In the Applied Artificial Intelligence context, this paper presents an agent software architecture using a model of agent. This architecture is composed of three abstract levels over which the complexity is distributed and reduced. The architecture is implemented in ReActalk, an open agent-oriented development tool, which was developed on top of Smalltalk-80. To illustrate our purpose and to validate the architecture, a simulation program to help in predicting volcanic eruptions was investigated. This program was run over a period of one year and has given many satisfying results unattainable up to there with more classical approaches.