This paper introduces Alpacas, a domain-specific language and algorithms aimed at architecture modeling and safety assessment for critical systems. It allows to study the effects of random and systematic faults on complex critical systems and their reliability. The underlying semantic framework of the language is Stochastic Guarded Transition Systems, for which Alpacas provides a feature-rich declarative modeling language and algorithms for symbolic analysis and Monte-Carlo simulation, allowing to compute safety indicators such as minimal cutsets and reliability. Built as a domain-specific language deeply embedded in Scala 3, Alpacas offers generic modeling capabilities and type-safety unparalleled in other existing safety assessment frameworks. This improved expressive power allows to address complex system modeling tasks, such as formalizing the architectural design space of a critical function, and exploring it to identify the most reliable variant. The features and algorithms of Alpacas are illustrated on a case study of a thrust allocation and power dispatch system for an electric vertical takeoff and landing aircraft.

Computational modelling of metabolic processes has proven to be a useful approach to formulate our knowledge and improve our understanding of core biochemical systems that are crucial to maintaining cellular functions. Towards understanding the broader role of metabolism on cellular decision-making in health and disease conditions, it is important to integrate the study of metabolism with other core regulatory systems and omics within the cell, including gene expression patterns. After quantitatively integrating gene expression profiles with a genome-scale reconstruction of human metabolism, we propose a set of combinatorial methods to reverse engineer gene expression profiles and to find pairs and higher-order combinations of genetic modifications that simultaneously optimize multi-objective cellular goals. This enables us to suggest classes of transcriptomic profiles that are most suitable to achieve given metabolic phenotypes. We demonstrate how our techniques are able to compute beneficial, neutral or "toxic" combinations of gene expression levels. We test our methods on nine tissue-specific cancer models, comparing our outcomes with the corresponding normal cells, identifying genes as targets for potential therapies. Our methods open the way to a broad class of applications that require an understanding of the interplay among genotype, metabolism, and cellular behaviour, at scale.

Summary Over the last few years, the complexity of web applications has increased to provide more dynamic web applications to users. The drawback of this complexity is the growing number of errors in the front‐end applications. In this paper, we present an approach to provide self‐healing for the web. We implemented this approach in two different tools: (i) BikiniProxy, an HTTP repair proxy, and (ii) BugBlock, a browser extension. They use five self‐healing strategies to rewrite the buggy HTML and JavaScript code to handle errors in web pages. We evaluate BikiniProxy and BugBlock with a new benchmark of 555 reproducible JavaScript errors of which 31.76% can be automatically self‐healed by BikiniProxy and 15.67% by BugBlock.

Over the last few years, the complexity of web applications has increased to provide more dynamic web applications to users. The drawback of this complexity is the growing number of errors in the front-end applications. In this paper, we present BikiniProxy, a novel technique to provide self-healing for the web. BikiniProxy is designed as an HTTP proxy that uses five self-healing strategies to rewrite the buggy HTML and Javascript code. We evaluate BikiniProxy with a new benchmark of 555 reproducible Javascript errors of which 31.76% can be automatically self-healed.

Modern programming frameworks come with large libraries, with diverse applications such as for matching regular expressions, parsing XML files and sending email. Programmers often use search engines such as Google and Bing to learn about existing APIs. In this paper, we describe SWIM, a tool which suggests code snippets given API-related natural language queries such as "generate md5 hash code". The query does not need to contain framework-specific trivia such as the type names or methods of interest.

StratEVO is an evolutionary algorithm that aims at generating strategies for the SMT solver Z3. Solving SAT modulo theories instance requires to define complex combinations of solvers, heuristics and proof checking tools that require expert knowledge. Our purpose is thus to show that an automated strategy generation process can be efficient and allows end-users to avoid difficult configuration tasks when using such solvers. StratEVO is evaluated on benchmarks from the 2014 and 2015 SMT competitions.

Satisfiability Modulo Theories (SMT) is essential for many practical applications, e.g., in hard- and software verification, and increasingly also in other scientific areas like computational biology. A large number of applications in these areas benefit from bit-precise reasoning over finite-domain variables. Current approaches in this area translate a formula over bit-vectors to an equisatisfiable propositional formula, which is then given to a SAT solver. In this paper, we present a novel stochastic local search (SLS) algorithm to solve SMT problems, especially those in the theory of bit-vectors, directly on the theory level. We explain how several successful techniques used in modern SLS solvers for SAT can be lifted to the SMT level. Experimental results show that our approach can compete with state-of-the-art bit-vector solvers on many practical instances and, sometimes, outperform existing solvers. This offers interesting possibilities in combining our approach with existing techniques, and, moreover, new insights into the importance of exploiting problem structure in SLS solvers for SAT. Our approach is modular and, therefore, extensible to support other theories, potentially allowing SLS to become part of the more general SMT framework.

This paper investigates the use of adaptive operator selection in the context of Local Search to solve a constraint satisfaction problem, namely the Progressive Party Problem. Operators are selected according to a utility value which is computed, for each operator, from the solution quality and from the distance of the candidate solution to recently visited solutions in the search trajectory. We show that using several non-problem-specific operators gives comparable successful resolution rates to an algorithm customized for the problem, albeit with slower run times.

This paper provides a broad overview of the situation in the area of Parallel Search with a specific focus on Parallel SAT Solving. A set of challenges to researchers is presented which, we believe, must be met to ensure the practical applicability of Parallel SAT Solvers in the future. All these challenges are described informally, but put into perspective with related research results, and a (subjective) grading of difficulty for each of them is provided.

This work presents the concept of Continuous Search (CS), which objective is to allow any user to eventually get their constraint solver achieving a top performance on their problems. Continuous Search comes in two modes: the functioning mode solves the user's problem instances using the current heuristics model; the exploration mode reuses these instances to train and improve the heuristics model through Machine Learning during the computer idle time. Contrasting with previous approaches, Continuous Search thus does not require that the representative instances needed to train a good heuristics model be available beforehand. It achieves lifelong learning, gradually becoming an expert on the user's problem instance distribution. Experimental validation suggests that Continuous Search can design efficient mixed strategies after considering a moderate number of problem instances.

Quantified constraint satisfaction problems have been the topic of an increasing number of studies for a few years. However, only sequential resolution algorithms have been proposed so far. This paper presents a parallel QCSP+ solving algorithm based on a problem-partition approach. It then discuss about work distribution policies and presents several experimental results comparing several parameters.

Motivated by the recent hardware evolution towards multi-core machines, we investigate parallel planning techniques in a shared-memory environment. We consider, more specifically, parallel versions of a best-first search algorithm that run K threads, each expanding the next best node from the open list. We show that the proposed technique has a number of advantages. First, it is (reasonably) simple: we show how the algorithm can be obtained from a sequential version mostly by adding parallel annotations. Second, we conduct an extensive empirical study that shows that this approach is quite effective. It is also dynamic in the sense that the number of nodes expanded in parallel is adapted during the search. Overall we show that the approach is promising for parallel domain-independent, suboptimal planning.

This paper presents an original dynamic subsumption technique for Boolean CNF formulae. It exploits simple and sufficient conditions to detect, during conflict analysis, clauses from the formula that can be reduced by subsumption. During the learnt clause derivation, and at each step of the associated resolution process, checks for backward subsumption between the current resolvent and clauses from the original formula are efficiently performed. The resulting method allows the dynamic removal of literals from the original clauses. Experimental results show that the integration of our dynamic subsumption technique within the state-of-the-art SAT solvers Minisat and Rsat particularly benefits to crafted problems.

In this paper, we present a new way to preprocess Boolean formulae in Conjunctive Normal Form (CNF). In contrast to most of the current pre-processing techniques, our approach aims at improving the filtering power of the original clauses while producing a small number of additional and relevant clauses. More precisely, an incomplete redundancy check is performed on each original clauses through unit propagation, leading to either a sub-clause or to a new relevant one generated by the clause learning scheme. This preprocessor is empirically compared to the best existing one in terms of size reduction and the ability to improve a state-of-the-art satisfiability solver.

The paper defines an automatic procedure for constructing a visually appealing collage from a collection of input images. The aim is that the resulting collage should be representative of the collection, summarising its main themes. It is also assembled largely seamlessly, using graph-cut, Poisson blending of alpha-masks, to hide the joins between input images. This paper makes several new contributions. Firstly, we show how energy terms can be included that: encourage the selection of a representative set of images; that are sensitive to particular object classes; that encourage a spatially efficient and seamless layout. Secondly the resulting optimization poses a search problem that, on the face of it, is computationally in-feasible. Rather than attempt an expensive, integrated optimization procedure, we have developed a sequence of optimization steps, from static ranking of images, through region of interest optimization, optimal packing by constraint satisfaction, and lastly graph-cut alpha-expansion. To illustrate the power of AutoCollage, we have used it to create collages of many home photo sets; we also conducted a user study in which AutoCollage outperformed competitive methods.

Internet data centers (IDCs) perform multi-customer hosting on a virtualized collection of resources while grid computing generalizes distributed computing by focusing on large scale resource sharing (I. Foster et al., 2001). When we consider the problem of resource allocation, the connection between grid and IDC is obvious. Indeed, both systems use similar resource reservation patterns. Mainly, service level agreement for IDC, and advanced resource reservation in grid systems (J. MacLaren, 2003). In each world, those reservation patterns are deemed to precisely represent resource requirements. This work presents an autonomous system for online resource allocations. The simulated architecture represents some IDC but our problem solving concepts are applicable to grid infrastructures. Our system takes advantage of monitoring information to reconsider its mathematical modelling of the components. This results in a continuous adaptation of the allocated resources.

The adaptation of software technology to distributed environments is an important challenge today. In this work we combine parallel and distributed search. By this way we add the potential speed-up of a parallel exploration in the processing of distributed problems. This paper extends DIBT a distributed search procedure operating in distributed constraint networks. The extension is twofold. First the procedure is updated to face delayed information problems upcoming in heterogeneous systems. Second, the search is extended to simultaneously explore independent parts of a distributed search tree. By this way we introduce parallelism into distributed search, which brings to interleaved distributed intelligent backtracking (IDIBT). Our results show that 1) insoluble problems do not greatly degrade performance over DIBT and 2) superlinear speed-up can be achieved when the distribution of solution is nonuniform.