Partial instantiation methods for inference in first-order logic

Satisfiability algorithms for propositional logic have improved enormously in recently years. This improvement increases the attractiveness of satisfiability methods for first-order logic that reduce the problem to a series of ground-level satisfiability problems. R. Jeroslow introduced a partial instantiation method of this kind that differs radically from the standard resolution-based methods. This paper lays the theoretical groundwork for an extension of his method that is general enough and efficient enough for general logic programming with indefinite clauses. In particular we improve Jeroslow's approach by (1) extending it to logic with functions, (2) accelerating it through the use of satisfiers, as introduced by Gallo and Rago, and (3) simplifying it to obtain further speedup. We provide a similar development for a "dual" partial instantiation approach defined by Hooker and suggest a primal-dual strategy. We prove correctness of the primal and dual algorithms for full first-order logic with functions, as well as termination on unsatisfiable formulas. We also report some preliminary computational results.

Site Characterization of Bangalore using Geophysical Method

A number of geophysical methods have been proposed for near-surface site characterization and measurement of shear wave velocity by using a great variety of testing configurations, processing techniques,and inversion algorithms. In particular, two widely-used techniques are SASW (Spectral Analysis of SurfaceWaves) and MASW (Multichannel Analysis of SurfaceWaves). MASW is increasingly being applied to earthquake geotechnical engineering for the local site characterization, microzonation and site response studies.A MASW is a geophysical method, which generates a shear-wave velocity (Vs) profile (i.e., Vs versus depth)by analyzing Raleigh-type surface waves on a multichannel record. MASW system consisting of 24 channels Geode seismograph with 24 geophones of 4.5 Hz frequency have been used in this investigation. For the site characterization program, the MASW field experiments consisting of 58 one-dimensional shear wave velocity tests and 20 two-dimensional shear wave tests have been carried out. The survey points have been selected in such a way that the results supposedly represent the whole metropolitan Bangalore having an area of 220 km2.The average shear wave velocity of Bangalore soils have been evaluated for depths of 5m, 10m, 15m, 20m, 25m and 30 m. The subsoil site classification has been made for seismic local site effect evaluation based on average shear wave velocity of 30m depth (Vs30) of sites using National Earthquake Hazards Reduction Program (NEHRP) and International Building Code (IBC) classification. Soil average shearwave velocity estimated based on overburden thickness from the borehole information is also presented. Mapping clearly indicates that the depth of soil obtained from MASW is closely matching with the soil layers in bore logs. Among total 55 locations of MASW survey carried out, 34 locations were very close to the SPT borehole locations and these are used to generate correlation between Vs and corrected “N” values. The SPT field “N” values are corrected by applying the NEHRP recommended corrections.

Facile synthesis of large area porous Cu2O as super hydrophobic yellow-red phosphors

By employing a thermal oxidation strategy, we have grown large area porous Cu2O from Cu foil. CuO nanorods are grown by heating Cu which were in turn heated in an argon atmosphere to obtain a porous Cu2O layer. The porous Cu2O layer is superhydrophobic and exhibits red luminescence. In contrast, Cu2O obtained by direct heating, is hydrophobic and exhibits yellow luminescence. Two more luminescence bands are observed in addition to red and yellow luminescence, corresponding to the recombination of free and bound excitons. Over all, the porous Cu2O obtained from Cu via CuO nanorods, can serve as a superhydrophobic luminescence/phosphor material.

Comparison of tertiary structures of proteins in protein-protein complexes with unbound forms suggests prevalence of allostery in signalling proteins

Abstract: Background: Most signalling and regulatory proteins participate in transient protein-protein interactions during biological processes. They usually serve as key regulators of various cellular processes and are often stable in both protein-bound and unbound forms. Availability of high-resolution structures of their unbound and bound forms provides an opportunity to understand the molecular mechanisms involved. In this work, we have addressed the question "What is the nature, extent, location and functional significance of structural changes which are associated with formation of protein-protein complexes?" Results: A database of 76 non-redundant sets of high resolution 3-D structures of protein-protein complexes, representing diverse functions, and corresponding unbound forms, has been used in this analysis. Structural changes associated with protein-protein complexation have been investigated using structural measures and Protein Blocks description. Our study highlights that significant structural rearrangement occurs on binding at the interface as well as at regions away from the interface to form a highly specific, stable and functional complex. Notably, predominantly unaltered interfaces interact mainly with interfaces undergoing substantial structural alterations, revealing the presence of at least one structural regulatory component in every complex. Interestingly, about one-half of the number of complexes, comprising largely of signalling proteins, show substantial localized structural change at surfaces away from the interface. Normal mode analysis and available information on functions on some of these complexes suggests that many of these changes are allosteric. This change is largely manifest in the proteins whose interfaces are altered upon binding, implicating structural change as the possible trigger of allosteric effect. Although large-scale studies of allostery induced by small-molecule effectors are available in literature, this is, to our knowledge, the first study indicating the prevalence of allostery induced by protein effectors. Conclusions: The enrichment of allosteric sites in signalling proteins, whose mutations commonly lead to diseases such as cancer, provides support for the usage of allosteric modulators in combating these diseases.

Algorithmic aspects of k-tuple total domination in graphs

For a fixed positive integer k, a k-tuple total dominating set of a graph G = (V. E) is a subset T D-k of V such that every vertex in V is adjacent to at least k vertices of T Dk. In minimum k-tuple total dominating set problem (MIN k-TUPLE TOTAL DOM SET), it is required to find a k-tuple total dominating set of minimum cardinality and DECIDE MIN k-TUPLE TOTAL DOM SET is the decision version of MIN k-TUPLE TOTAL DOM SET problem. In this paper, we show that DECIDE MIN k-TUPLE TOTAL DOM SET is NP-complete for split graphs, doubly chordal graphs and bipartite graphs. For chordal bipartite graphs, we show that MIN k-TUPLE TOTAL DOM SET can be solved in polynomial time. We also propose some hardness results and approximation algorithms for MIN k-TUPLE TOTAL DOM SET problem. (c) 2012 Elsevier B.V. All rights reserved.

Thermodynamics of higher spin black holes in 3D

We examine the thermodynamic properties of recently constructed black hole solutions in SL(3, R) x SL(3, R) Chern-Simons theory in the presence of a chemical potential for spin-3 charge, which acts as an irrelevant deformation of the dual CFT with W-3 X W-3 symmetry. The smoothness or holonomy conditions admit four branches of solutions describing a flow between two AdS(3) backgrounds corresponding to two different CFTs. The dominant branch at low temperatures, connected to the BTZ black hole, merges smoothly with a thermodynamically unstable branch and disappears at higher temperatures. We confirm that the UV region of the flow satisfies the Ward identities of a CFT with W-3((2)) x W-3((2)) symmetry deformed by a spin-3/2 current. This allows to identify the precise map between UV and HI thermodynamic variables. We find that the high temperature regime is dominated by a black hole branch whose thermodynamics can only be consistently inferred with reference to this W-3((2)) x W-3((2)) CFT.

OTCYMIST: Otsu-Canny minimal spanning tree for born-digital images

Text segmentation and localization algorithms are proposed for the born-digital image dataset. Binarization and edge detection are separately carried out on the three colour planes of the image. Connected components (CC's) obtained from the binarized image are thresholded based on their area and aspect ratio. CC's which contain sufficient edge pixels are retained. A novel approach is presented, where the text components are represented as nodes of a graph. Nodes correspond to the centroids of the individual CC's. Long edges are broken from the minimum spanning tree of the graph. Pair wise height ratio is also used to remove likely non-text components. A new minimum spanning tree is created from the remaining nodes. Horizontal grouping is performed on the CC's to generate bounding boxes of text strings. Overlapping bounding boxes are removed using an overlap area threshold. Non-overlapping and minimally overlapping bounding boxes are used for text segmentation. Vertical splitting is applied to generate bounding boxes at the word level. The proposed method is applied on all the images of the test dataset and values of precision, recall and H-mean are obtained using different approaches.

Modified roaming optimization for multi-modal optima

This paper explains the algorithm of Modified Roaming Optimization (MRO) for capturing the multiple optima for multimodal functions. There are some similarities between the Roaming Optimization (RO) and MRO algorithms, but the MRO algorithm is created to overcome the problems facing while applying the RO to the problems possessing large number of solutions. The MRO mainly uses the concept of density to overcome the challenges posed by RO. The algorithm is tested with standard test functions and also discussions are made to improve the efficacy of the MRO algorithm. This paper also gives the results of MRO applied for solving Inverse Kinematics (IK) problem for SCARA and PUMA robots.

Surrogate Regret Bounds for Bipartite Ranking via Strongly Proper Losses

The problem of bipartite ranking, where instances are labeled positive or negative and the goal is to learn a scoring function that minimizes the probability of mis-ranking a pair of positive and negative instances (or equivalently, that maximizes the area under the ROC curve), has been widely studied in recent years. A dominant theoretical and algorithmic framework for the problem has been to reduce bipartite ranking to pairwise classification; in particular, it is well known that the bipartite ranking regret can be formulated as a pairwise classification regret, which in turn can be upper bounded using usual regret bounds for classification problems. Recently, Kotlowski et al. (2011) showed regret bounds for bipartite ranking in terms of the regret associated with balanced versions of the standard (non-pairwise) logistic and exponential losses. In this paper, we show that such (non-pairwise) surrogate regret bounds for bipartite ranking can be obtained in terms of a broad class of proper (composite) losses that we term as strongly proper. Our proof technique is much simpler than that of Kotlowski et al. (2011), and relies on properties of proper (composite) losses as elucidated recently by Reid and Williamson (2010, 2011) and others. Our result yields explicit surrogate bounds (with no hidden balancing terms) in terms of a variety of strongly proper losses, including for example logistic, exponential, squared and squared hinge losses as special cases. An important consequence is that standard algorithms minimizing a (non-pairwise) strongly proper loss, such as logistic regression and boosting algorithms (assuming a universal function class and appropriate regularization), are in fact consistent for bipartite ranking; moreover, our results allow us to quantify the bipartite ranking regret in terms of the corresponding surrogate regret. We also obtain tighter surrogate bounds under certain low-noise conditions via a recent result of Clemencon and Robbiano (2011).

A Multi-phase Approach for Improving Information Diffusion in Social Networks

For maximizing influence spread in a social network, given a certain budget on the number of seed nodes, we investigate the effects of selecting and activating the seed nodes in multiple phases. In particular, we formulate an appropriate objective function for two-phase influence maximization under the independent cascade model, investigate its properties, and propose algorithms for determining the seed nodes in the two phases. We also study the problem of determining an optimal budget-split and delay between the two phases.

SeamSeg: Video Object Segmentation using Patch Seams

In this paper, we propose a technique for video object segmentation using patch seams across frames. Typically, seams, which are connected paths of low energy, are utilised for retargeting, where the primary aim is to reduce the image size while preserving the salient image contents. Here, we adapt the formulation of seams for temporal label propagation. The energy function associated with the proposed video seams provides temporal linking of patches across frames, to accurately segment the object. The proposed energy function takes into account the similarity of patches along the seam, temporal consistency of motion and spatial coherency of seams. Label propagation is achieved with high fidelity in the critical boundary regions, utilising the proposed patch seams. To achieve this without additional overheads, we curtail the error propagation by formulating boundary regions as rough-sets. The proposed approach out-perform state-of-the-art supervised and unsupervised algorithms, on benchmark datasets.

Falcon: A Graph Manipulation Language for Heterogeneous Systems

Graph algorithms have been shown to possess enough parallelism to keep several computing resources busy-even hundreds of cores on a GPU. Unfortunately, tuning their implementation for efficient execution on a particular hardware configuration of heterogeneous systems consisting of multicore CPUs and GPUs is challenging, time consuming, and error prone. To address these issues, we propose a domain-specific language (DSL), Falcon, for implementing graph algorithms that (i) abstracts the hardware, (ii) provides constructs to write explicitly parallel programs at a higher level, and (iii) can work with general algorithms that may change the graph structure (morph algorithms). We illustrate the usage of our DSL to implement local computation algorithms (that do not change the graph structure) and morph algorithms such as Delaunay mesh refinement, survey propagation, and dynamic SSSP on GPU and multicore CPUs. Using a set of benchmark graphs, we illustrate that the generated code performs close to the state-of-the-art hand-tuned implementations.