Minimal unsatisfiable sets: Classification and bounds

Proving the unsatisfiability of propositional Boolean formulas has applications in a wide range of fields. Minimal Unsatisfiable Sets (MUS) are signatures of the property of unsatisfiability in formulas and our understanding of these signatures can be very helpful in answering various algorithmic and structural questions relating to unsatisfiability. In this paper, we explore some combinatorial properties of MUS and use them to devise a classification scheme for MUS. We also derive bounds on the sizes of MUS in Horn, 2-SAT and 3-SAT formulas.

Fuzzy Expert Approach with Curtailed Controllers for Improved Reactive Power Dispatch

This paper addresses the problem of curtailing the number of control actions using fuzzy expert approach for voltage/reactive power dispatch. It presents an approach using fuzzy set theory for reactive power control with the purpose of improving the voltage profile of a power system. To minimize the voltage deviations from pre-desired values of all the load buses, using the sensitivities with respect to reactive power control variables form the basis of the proposed Fuzzy Logic Control (FLC). Control variables considered are switchable VAR compensators, On Load Tap Changing (OLTC) transformers and generator excitations. Voltage deviations and controlling variables are translated into fuzzy set notations to formulate the relation between voltage deviations and controlling ability of controlling devices. The developed fuzzy system is tested on a few simulated practical Indian power systems and modified IEEE-30 bus system. The performance of the fuzzy system is compared with conventional optimization technique and results obtained are encouraging. Results obtained for a modified IEEE-30 bus test system and a 205-node equivalent EHV system a part of Indian southern grid are presented for illustration purposes. The proposed fuzzy-expert technique is found suitable for on-line applications in energy control centre as the solution is obtained fast with significant speedups with few number of controllers.

Badly approximable numbers and vectors in Cantor-like sets

We show that a large class of Cantor-like sets of R-d, d >= 1, contains uncountably many badly approximable numbers, respectively badly approximable vectors, when d >= 2. An analogous result is also proved for subsets of R-d arising in the study of geodesic flows corresponding to (d+1)-dimensional manifolds of constant negative curvature and finite volume, generalizing the set of badly approximable numbers in R. Furthermore, we describe a condition on sets, which is fulfilled by a large class, ensuring a large intersection with these Cantor-like sets.

Rainbow connection number and connected dominating sets

The rainbow connection number of a connected graph is the minimum number of colors needed to color its edges, so that every pair of its vertices is connected by at least one path in which no two edges are colored the same. In this article we show that for every connected graph on n vertices with minimum degree delta, the rainbow connection number is upper bounded by 3n/(delta + 1) + 3. This solves an open problem from Schiermeyer (Combinatorial Algorithms, Springer, Berlin/Hiedelberg, 2009, pp. 432437), improving the previously best known bound of 20n/delta (J Graph Theory 63 (2010), 185191). This bound is tight up to additive factors by a construction mentioned in Caro et al. (Electr J Combin 15(R57) (2008), 1). As an intermediate step we obtain an upper bound of 3n/(delta + 1) - 2 on the size of a connected two-step dominating set in a connected graph of order n and minimum degree d. This bound is tight up to an additive constant of 2. This result may be of independent interest. We also show that for every connected graph G with minimum degree at least 2, the rainbow connection number, rc(G), is upper bounded by Gc(G) + 2, where Gc(G) is the connected domination number of G. Bounds of the form diameter(G)?rc(G)?diameter(G) + c, 1?c?4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, asteroidal triple-free graphs, circular arc graphs, threshold graphs, and chain graphs all with minimum degree delta at least 2 and connected. We also show that every bridge-less chordal graph G has rc(G)?3.radius(G). In most of these cases, we also demonstrate the tightness of the bounds.

Maximum weight independent sets in hole- and dart-free graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for hole-free graphs is unknown. In this paper, we first prove that the MWIS problem for (hole, dart, gem)-free graphs can be solved in O(n(3))-time. By using this result, we prove that the MWIS problem for (hole, dart)-free graphs can be solved in O(n(4))-time. Though the MWIS problem for (hole, dart, gem)-free graphs is used as a subroutine, we also give the best known time bound for the solvability of the MWIS problem in (hole, dart, gem)-free graphs. (C) 2012 Elsevier B.V. All rights reserved.

A numerical approach to determine the sufficiency of given boundary data sets for uniquely estimating interior elastic properties

We consider an inverse elasticity problem in which forces and displacements are known on the boundary and the material property distribution inside the body is to be found. In other words, we need to estimate the distribution of constitutive properties using the finite boundary data sets. Uniqueness of the solution to this problem is proved in the literature only under certain assumptions for a given complete Dirichlet-to-Neumann map. Another complication in the numerical solution of this problem is that the number of boundary data sets needed to establish uniqueness is not known even under the restricted cases where uniqueness is proved theoretically. In this paper, we present a numerical technique that can assess the sufficiency of given boundary data sets by computing the rank of a sensitivity matrix that arises in the Gauss-Newton method used to solve the problem. Numerical experiments are presented to illustrate the method.

An Optimal Fuzzy Logic Controller tuned with Artificial Immune System

In this paper, a method for the tuning the membership functions of a Mamdani type Fuzzy Logic Controller (FLC) using the Clonal Selection Algorithm(CSA) a model of the Artificial Immune System(AIS) paradigm is examined. FLC's are designed for two problems, firstly the linear cart centering problem and secondly the highly nonlinear inverted pendulum problem. The FLC tuned by AIS is compared with FLC tuned by GA. In order to check the robustness of the designed PLC's white noise was added to the system, further, the masses of the cart and the length and mass of the pendulum are changed. The PLC's were also tested in the presence of faulty rules. Finally, Kruskal Wallis test was performed to compare the performance of the GA and AIS. An insight into the algorithms are also given by studying the effect of the important parameters of GA and AIS.

Network congestion management by fuzzy inference using virtual flows

Effective network overload alleviation is very much essential in order to maintain security and integrity from the operational viewpoint of deregulated power systems. This paper aims at developing a methodology to reschedule the active power generation from the sources in order to manage the network congestion under normal/contingency conditions. An effective method has been proposed using fuzzy rule based inference system. Using virtual flows concept, which provides partial contributions/counter flows in the network elements is used as a basis in the proposed method to manage network congestions to the possible extent. The proposed method is illustrated on a sample 6 bus test system and on modified IEEE 39 bus system.

Benchmarking recognition results on camera captured word image data sets

We have benchmarked the maximum obtainable recognition accuracy on five publicly available standard word image data sets using semi-automated segmentation and a commercial OCR. These images have been cropped from camera captured scene images, born digital images (BDI) and street view images. Using the Matlab based tool developed by us, we have annotated at the pixel level more than 3600 word images from the five data sets. The word images binarized by the tool, as well as by our own midline analysis and propagation of segmentation (MAPS) algorithm are recognized using the trial version of Nuance Omnipage OCR and these two results are compared with the best reported in the literature. The benchmark word recognition rates obtained on ICDAR 2003, Sign evaluation, Street view, Born-digital and ICDAR 2011 data sets are 83.9%, 89.3%, 79.6%, 88.5% and 86.7%, respectively. The results obtained from MAPS binarized word images without the use of any lexicon are 64.5% and 71.7% for ICDAR 2003 and 2011 respectively, and these values are higher than the best reported values in the literature of 61.1% and 41.2%, respectively. MAPS results of 82.8% for BDI 2011 dataset matches the performance of the state of the art method based on power law transform.

Covariance profiles: a signature representation for object sets

We consider the problem of extracting a signature representation of similar entities employing covariance descriptors. Covariance descriptors can efficiently represent objects and are robust to scale and pose changes. We posit that covariance descriptors corresponding to similar objects share a common geometrical structure which can be extracted through joint diagonalization. We term this diagonalizing matrix as the Covariance Profile (CP). CP can be used to measure the distance of a novel object to an object set through the diagonality measure. We demonstrate how CP can be employed on images as well as for videos, for applications such as face recognition and object-track clustering.

Fuzzy data envelopment analysis for performance evaluation of an irrigation system

Sixteen irrigation subsystems of the Mahi Bajaj Sagar Project, Rajasthan, India, are evaluated and selection of the most suitable/best is made using data envelopment analysis (DEA) in both deterministic and fuzzy environments. Seven performance-related indicators, namely, land development works (LDW), timely supply of inputs (TSI), conjunctive use of water resources (CUW), participation of farmers (PF), environmental conservation (EC), economic impact (EI) and crop productivity (CPR) are considered. Of the seven, LDW, TSI, CUW, PF and EC are considered inputs, whereas CPR and EI are considered outputs for DEA modelling purposes. Spearman rank correlation coefficient values are also computed for various scenarios. It is concluded that DEA in both deterministic and fuzzy environments is useful for the present problem. However, the outcome of fuzzy DEA may be explored for further analysis due to its simple, effective data and discrimination handling procedure. It is inferred that the present study can be explored for similar situations with suitable modifications.

Gene expression programming-fuzzy logic method for crop type classification

Crop type classification using remote sensing data plays a vital role in planning cultivation activities and for optimal usage of the available fertile land. Thus a reliable and precise classification of agricultural crops can help improve agricultural productivity. Hence in this paper a gene expression programming based fuzzy logic approach for multiclass crop classification using Multispectral satellite image is proposed. The purpose of this work is to utilize the optimization capabilities of GEP for tuning the fuzzy membership functions. The capabilities of GEP as a classifier is also studied. The proposed method is compared to Bayesian and Maximum likelihood classifier in terms of performance evaluation. From the results we can conclude that the proposed method is effective for classification.

Black hole formation in fuzzy sphere collapse

We study the collapse of a fuzzy sphere, that is a spherical membrane built out of D0-branes, in the Banks-Fischler-Shenker-Susskind model. At weak coupling, as the sphere shrinks, open strings are produced. If the initial radius is large then open string production is not important and the sphere behaves classically. At intermediate initial radius the backreaction from open string production is important but the fuzzy sphere retains its identity. At small initial radius the sphere collapses to form a black hole. The crossover between the later two regimes is smooth and occurs at the correspondence point of Horowitz and Polchinski.