Delayed theory combination vs. Nelson-Oppen for satisfiability modulo theories: a comparative analysis

Most state-of-the-art approaches for Satisfiability Modulo Theories $(SMT(\mathcal{T}))$ rely on the integration between a SAT solver and a decision procedure for sets of literals in the background theory $\mathcal{T} (\mathcal{T}{\text {-}}solver)$ . Often $\mathcal{T}$ is the combination $\mathcal{T}_1 \cup \mathcal{T}_2$ of two (or more) simpler theories $(SMT(\mathcal{T}_1 \cup \mathcal{T}_2))$ , s.t. the specific ${\mathcal{T}_i}{\text {-}}solvers$ must be combined. Up to a few years ago, the standard approach to $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ was to integrate the SAT solver with one combined $\mathcal{T}_1 \cup \mathcal{T}_2{\text {-}}solver$ , obtained from two distinct ${\mathcal{T}_i}{\text {-}}solvers$ by means of evolutions of Nelson and Oppen’s (NO) combination procedure, in which the ${\mathcal{T}_i}{\text {-}}solvers$ deduce and exchange interface equalities. Nowadays many state-of-the-art SMT solvers use evolutions of a more recent $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ procedure called Delayed Theory Combination (DTC), in which each ${\mathcal{T}_i}{\text {-}}solver$ interacts directly and only with the SAT solver, in such a way that part or all of the (possibly very expensive) reasoning effort on interface equalities is delegated to the SAT solver itself. In this paper we present a comparative analysis of DTC vs. NO for $SMT(\mathcal{T}_1 \cup \mathcal{T}_2)$ . On the one hand, we explain the advantages of DTC in exploiting the power of modern SAT solvers to reduce the search. On the other hand, we show that the extra amount of Boolean search required to the SAT solver can be controlled. In fact, we prove two novel theoretical results, for both convex and non-convex theories and for different deduction capabilities of the ${\mathcal{T}_i}{\text {-}}solvers$ , which relate the amount of extra Boolean search required to the SAT solver by DTC with the number of deductions and case-splits required to the ${\mathcal{T}_i}{\text {-}}solvers$ by NO in order to perform the same tasks: (i) under the same hypotheses of deduction capabilities of the ${\mathcal{T}_i}{\text {-}}solvers$ required by NO, DTC causes no extra Boolean search; (ii) using ${\mathcal{T}_i}{\text {-}}solvers$ with limited or no deduction capabilities, the extra Boolean search required can be reduced down to a negligible amount by controlling the quality of the $\mathcal{T}$ -conflict sets returned by the ${\mathcal{T}_i}{\text {-}}solvers$ .     

Cost-Based Filtering Techniques for Stochastic Inventory Control Under Service Level Constraints

This paper¹ considers a single product and a single stocking location production/inventory control problem given a non-stationary stochastic demand. Under a widely-used control policy for this type of inventory system, the objective is to find the optimal number of replenishments, their timings and their respective order-up-to-levels that meet customer demands to a required service level. We extend a known CP approach for this problem using three cost-based filtering methods. Our approach can solve to optimality instances of realistic size much more efficiently than previous approaches, often with no search effort at all. This work was supported by Science Foundation Ireland under Grant No. 03/CE3/I405 as part of the Centre for Telecommunications Value-Chain-Driven Research (CTVR) and Grant No. 00/PI.1/C075. ¹This paper is an extended version of [19].     

A class of high performance Maekawa-type algorithms for distributed systems under heavy demand

Summary Distributed Mutual Exclusion algorithms have been mainly compared using the number of messages exchanged per critical section execution. In such algorithms, no attention has been paid to the serialization order of the requests. Indeed, they adopt FCFS discipline. Conversely, the insertion of priority serialization disciplines, such as Short-Job-First, Head-Of-Line, Shortest-Remaining-Job-First etc., can be useful in many applications to optimize some performance indices. However, such priority disciplines are prone to starvation. The goal of this paper is to investigate and evaluate the impact of the insertion of a priority discipline in Maekawa-type algorithms. Priority serialization disciplines will be inserted by means of agated batch mechanism which avoids starvation. In a distributed algorithm, such a mechanism needs synchronizations among the processes. In order to highlight the usefulness of the priority based serialization discipline, we show how it can be used to improve theaverage response time compared to the FCFS discipline. The gated batch approach exhibits other advantages: algorithms are inherently deadlock-free and messages do not need to piggyback timestamps. We also show that, under heavy demand, algorithms using gated batch exchange less messages than Maekawa-type algorithms per critical section excution. Roberto Baldoni was born in Rome on February 1, 1965. He received the Laurea degree in electronic engineering in 1990 from the University of Rome La Sapienza and the Ph.D. degree in Computer Science from the University of Rome La Sapienza in 1994. Currently, he is a researcher in computer science at IRISA, Rennes (France). His research interests include operating systems, distributed algorithms, network protocols and real-time multimedia applications. Bruno Ciciani received the Laurea degree in electronic engineering in 1980 from the University of Rome La Sapienza. From 1983 to 1991 he has been a researcher at the University of Rome Tor Vergata. He is currently full professor in Computer Science at the University of Rome La Sapienza. His research activities include distributed computer systems, fault-tolerant computing, languages for parallel processing, and computer system performance and reliability evaluation. He has published in IEEE Trans. on Computers, IEEE Trans. on Knowledge and Data Engineering, IEEE Trans. on Software Engineering and IEEE Trans. on Reliability. He is the author of a book titled Manufactoring Yield Evaluation of VLSI/WSI Systems to be published by IEEE Computer Society Press.This research was supported in part by the Consiglio Nazionale delle Ricerche under grant 93.02294.CT12This author is also supported by a grant of the Human Capital and Mobility project of the European Community under contract No. 3702 CABERNET     

Light Controlled Biohybrid Microbots

Biohybrid microbots integrate biological actuators and sensors into synthetic chassis with the aim of providing the building blocks of next-generation micro-robotics. One of the main challenges is the development of self-assembled systems with consistent behavior and such that they can be controlled independently to perform complex tasks. Herein, it is shown that, using light-driven bacteria as propellers, 3D printed microbots can be steered by unbalancing light intensity over different microbot parts. An optimal feedback loop is designed in which a central computer projects onto each microbot a tailor-made light pattern, calculated from its position and orientation. In this way, multiple microbots can be independently guided through a series of spatially distributed checkpoints. By exploiting a natural light-driven proton pump, these bio-hybrid microbots are able to extract mechanical energy from light with such high efficiency that, in principle, hundreds of these systems can be controlled simultaneously with a total optical power of just a few milliwatts.     

Photocatalytic activity of a new composite material of Fe (III) oxide nanoparticles wrapped by a matrix of polymeric carbon nitride and amorphous carbon

Polymeric carbon nitride was synthesized from urea and doped with Cu and Fe to act as co-catalysts. The material doped with Fe was a new composite material composed of Fe(III) oxides (acting as a co-catalyst) wrapped by the polymer layers and amorphous carbon. Furthermore, the copper doped material was described in a previous report. The photocatalytic degradation of the azo dye direct blue 1 (DB) was studied using as photocatalysts: pure carbon nitride (CN), carbon nitride doped with Cu (CN-Cu) and carbon nitride doped with Fe (CN-Fe). The catalysts were characterized by Fourier transform infrared (FTIR) spectroscopy, X-ray diffraction (XRD), by X-ray photoelectron spectroscopy (XPS) and Brunauer–Emmett–Teller method (BET), etc. The adsorption phenomenon was studied using the Langmuir and Freundlich models. For the kinetic study, a solution of 500 mg L^?1 of DB1 was treated with each catalyst, visible light and H₂O₂. The dye concentration was measured by spectrophotometry at the wavelength of 565 nm, and the removal of the total organic content (TOC) was quantified. BET analysis yielded surface areas of 60.029, 20.116 and 70.662 m²g^?1 for CN, CN-Cu and CN-Fe, respectively. The kinetics of degradation were pseudo-first order, whose constants were 0.093, 0.039 and 0.110 min^?1 for CN, CN-Cu and CN-Fe, respectively. The total organic carbon (TOC) removal reached the highest value of 14.46% with CN-Fe.     

How can Cleaner Production practices contribute to meet ISO 14001 requirements? Critical analysis from a survey with industrial companies

The companies’ needs to adopt changes in their way of production to maximize the environmental performance required by their stakeholders, and at the same time, to maximize their economic and market performance, have made them seek for environmental strategies and certifications. In this sense, the Cleaner Production and the Environmental Management System based on ISO 14001 have been, respectively, presented, since the main objective of this research is to identify and analyze Cleaner Production contributions to comply with ISO 14001 requirements. For such, a survey research has been carried out in Brazilian industrial companies certified by ISO 14001. We have identified the main performance factors by leading practices and variables of Cleaner Production that contribute to the compliance with the standard requirements by companies. Thus, it has been noted that Cleaner Production is an important strategy for the preparation of companies for certification as well as for improving their environmental performance.     

Engineered Multifunctional Albumin‐Decorated Porous Silicon Nanoparticles for FcRn Translocation of Insulin

The last decade has seen remarkable advances in the development of drug delivery systems as alternative to parenteral injection‐based delivery of insulin. Neonatal Fc receptor (FcRn)‐mediated transcytosis has been recently proposed as a strategy to increase the transport of drugs across the intestinal epithelium. FcRn‐targeted nanoparticles (NPs) could hijack the FcRn transcytotic pathway and cross the epithelial cell layer. In this study, a novel nanoparticulate system for insulin delivery based on porous silicon NPs is proposed. After surface conjugation with albumin and loading with insulin, the NPs are encapsulated into a pH‐responsive polymeric particle by nanoprecipitation. The developed NP formulation shows controlled size and homogeneous size distribution. Transmission electron microscopy (TEM) images show successful encapsulation of the NPs into pH‐sensitive polymeric particles. No insulin release is detected at acidic conditions, but a controlled release profile is observed at intestinal pH. Toxicity studies show high compatibility of the NPs with intestinal cells. In vitro insulin permeation across the intestinal epithelium shows approximately fivefold increase when insulin is loaded into FcRn‐targeted NPs. Overall, these FcRn‐targeted NPs offer a toolbox in the development of targeted therapies for oral delivery of insulin.     

Chemiotropic behavior of female olive fly (Bactrocera oleae GMEL.) onOlea europaea L

An interpretation is given of a number of observations on the chemiotropic behavior ofBactrocera oleae in connection with olive maceration water and the fly's return to the olive groves after the first summer rains. To this end, the headspace of both maceration water and leaf leaching water, simulating rainfall, were examined. In both cases, the presence of ammonia, which is generally known to attract fruit flies (Diptera, Tephritidae), was detected and, for the first time, in addition to other compounds that are inert for the fly, the presence of styrene was also detected. This aromatic hydrocarbon was found to be a strong attractant. It is shown that both ammonia and styrene are products of the metabolism of microbial flora present on the olive and leaf surface.     

On the Construction of Classes of Suffix Trees for Square Matrices: Algorithms and Applications

We provide a uniform framework for the study of index data structures for a two-dimensional matrixTEXT[1:n, 1:n] whose entries are drawn from an ordered alphabetΣ. An index forTEXTcan be informally seen as the two-dimensional analog of the suffix tree for a string. It allows on-line searches and statistics to be performed onTEXTby representing compactly theΘ(n³) square submatrices ofTEXTin optimalO(n²) space. We identify 4ⁿ⁻¹families of indices forTEXT, each containing ∏ⁿ_i=1 (2i−1)! isomorphic data structures. We also develop techniques leading to a single algorithm that efficiently builds any index in any family inO(n² log n) time andO(n²) space. Such an algorithm improves in various respects the algorithms for the construction of the PAT tree and the Lsuffix tree. The framework and the algorithm easily generalize tod>2 dimensions. Moreover, as part of our algorithm, we provide new algorithmic tools that yield a space-efficient implementation of the “naming scheme” of R. Karpet al.(in“Proceedings, Fourth Symposium on Theory of Computing,” pp. 125–136) for strings and matrices.