Precise Slicing in Imperative Programs via Term-Rewriting and Abstract Interpretation

We propose a new approach for producing precise constrained slices of programs in a language such as C. We build upon a previous approach for this problem, which is based on term-rewriting, which primarily targets loop-free fragments and is fully precise in this setting. We incorporate abstract interpretation into term-rewriting, using a given arbitrary abstract lattice, resulting in a novel technique for slicing loops whose precision is linked to the power of the given abstract lattice. We address pointers in a first-class manner, including when they are used within loops to traverse and update recursive data structures. Finally, we illustrate the comparative precision of our slices over those of previous approaches using representative examples.

Checking Liveness Properties of Presburger Counter Systems Using Reachability Analysis

Counter systems are a well-known and powerful modeling notation for specifying infinite-state systems. In this paper we target the problem of checking liveness properties in counter systems. We propose two semi decision techniques towards this, both of which return a formula that encodes the set of reachable states of the system that satisfy a given liveness property. A novel aspect of our techniques is that they use reachability analysis techniques, which are well studied in the literature, as black boxes, and are hence able to compute precise answers on a much wider class of systems than previous approaches for the same problem. Secondly, they compute their results by iterative expansion or contraction, and hence permit an approximate solution to be obtained at any point. We state the formal properties of our techniques, and also provide experimental results using standard benchmarks to show the usefulness of our approaches. Finally, we sketch an extension of our liveness checking approach to check general CTL properties.

Fixed-orientation equilateral triangle matching of point sets

Given a point set P and a class C of geometric objects, G(C)(P) is a geometric graph with vertex set P such that any two vertices p and q are adjacent if and only if there is some C is an element of C containing both p and q but no other points from P. We study G(del)(P) graphs where del is the class of downward equilateral triangles (i.e., equilateral triangles with one of their sides parallel to the x-axis and the corner opposite to this side below that side). For point sets in general position, these graphs have been shown to be equivalent to half-Theta(6) graphs and TD-Delaunay graphs. The main result in our paper is that for point sets P in general position, G(del)(P) always contains a matching of size at least vertical bar P vertical bar-1/3] and this bound is tight. We also give some structural properties of G(star)(P) graphs, where is the class which contains both upward and downward equilateral triangles. We show that for point sets in general position, the block cut point graph of G(star)(P) is simply a path. Through the equivalence of G(star)(P) graphs with Theta(6) graphs, we also derive that any Theta(6) graph can have at most 5n-11 edges, for point sets in general position. (C) 2013 Elsevier B.V. All rights reserved.

Haemophilus influenzae Genome Database (HIGDB): A single point web resource for Haemophilus influenzae

Background: Haemophilus influenzae (H. Influenzae) is the causative agent of pneumonia, bacteraemia and meningitis. The organism is responsible for large number of deaths in both developed and developing countries. Even-though the first bacterial genome to be sequenced was that of H. Influenzae, there is no exclusive database dedicated for H. Influenzae. This prompted us to develop the Haemophilus influenzae Genome Database (HIGDB). Methods: All data of HIGDB are stored and managed in MySQL database. The HIGDB is hosted on Solaris server and developed using PERL modules. Ajax and JavaScript are used for the interface development. Results: The HIGDB contains detailed information on 42,741 proteins, 18,077 genes including 10 whole genome sequences and also 284 three dimensional structures of proteins of H. influenzae. In addition, the database provides ``Motif search'' and ``GBrowse''. The HIGDB is freely accessible through the URL:http://bioserverl.physicslisc.ernetin/HIGDB/. Discussion: The HIGDB will be a single point access for bacteriological, clinical, genomic and proteomic information of H. influenzae. The database can also be used to identify DNA motifs within H. influenzae genomes and to compare gene or protein sequences of a particular strain with other strains of H. influenzae. (C) 2014 Elsevier Ltd. All rights reserved.

Two-point correlation function of an exclusion process with hole-dependent rates

We consider an exclusion process on a ring in which a particle hops to an empty neighboring site with a rate that depends on the number of vacancies n in front of it. In the steady state, using the well-known mapping of this model to the zero-range process, we write down an exact formula for the partition function and the particle-particle correlation function in the canonical ensemble. In the thermodynamic limit, we find a simple analytical expression for the generating function of the correlation function. This result is applied to the hop rate u(n) = 1 + (b/n) for which a phase transition between high-density laminar phase and low-density jammed phase occurs for b > 2. For these rates, we find that at the critical density, the correlation function decays algebraically with a continuously varying exponent b - 2. We also calculate the two-point correlation function above the critical density and find that the correlation length diverges with a critical exponent nu = 1/(b - 2) for b < 3 and 1 for b > 3. These results are compared with those obtained using an exact series expansion for finite systems.

Experimental Characterization and Control of Miniaturized Pneumatic Artificial Muscle

Robotic surgical tools used in minimally invasive surgeries (MIS) require miniaturized and reliable actuators for precise positioning and control of the end-effector. Miniature pneumatic artificial muscles (MPAMs) are a good choice due to their inert nature, high force to weight ratio, and fast actuation. In this paper, we present the development of miniaturized braided pneumatic muscles with an outer diameter of similar to 1.2 mm, a high contraction ratio of about 18%, and capable of providing a pull force in excess of 4 N at a supply pressure of 0.8 MPa. We present the details of the developed experimental setup, experimental data on contraction and force as a function of applied pressure, and characterization of the MPAM. We also present a simple kinematics and experimental data based model of the braided pneumatic muscle and show that the model predicts contraction in length to within 20% of the measured value. Finally, a robust controller for the MPAMs is developed and validated with experiments and it is shown that the MPAMs have a time constant of similar to 10 ms thereby making them suitable for actuating endoscopic and robotic surgical tools.

Low tension strings on a cosmological singularity

It has recently been argued that the singularity of the Milne orbifold can be resolved in higher spin theories. In string theory scattering amplitudes, however, the Milne singularity gives rise to ultraviolet divergences that signal uncontrolled backreaction. Since string theory in the low tension limit is expected to be a higher spin theory (although precise proposals only exist in special cases), we investigate what happens to these scattering amplitudes in the low tension limit. We point out that the known problematic ultraviolet divergences disappear in this limit. In addition we systematically identify all divergences of the simplest 2-to-2 tree-level string scattering amplitude on the Milne orbifold, and argue that the divergences that survive in the low tension limit have sensible infrared interpretations.

Transitory second-order reciprocal connection for two surfaces in point contact

This paper investigates the instantaneous spatial higher pair to lower pair substitute-connection which is kinematically equivalent up to acceleration analysis for two smooth surfaces in point contact. The existing first-order equivalent substitute-connection consisting of a Hooke's joint (U-joint) and a spherical joint (S-joint) connected by an additional link is extended up to second-order. A two step procedure is chalked out for achieving this equivalence. First, the existing method is employed for velocity equivalence. In the second step, the two centers of substitution are obtained as a conjugate relationship involving the principal normal curvatures of the surfaces at the contact point and the screw coordinates of the instantaneous screw axis (ISA) of the first-order relative motion. Unlike the classical planar replacement, this particular substitution cannot be done by merely examining the profiles of the contacting surfaces. An illustrative example of a three-link direct-contact mechanism is presented. (C) 2014 Elsevier Ltd. All rights reserved.

GLOBAL REGISTRATION OF MULTIPLE POINT CLOUDS USING SEMIDEFINITE PROGRAMMING

Consider N points in R-d and M local coordinate systems that are related through unknown rigid transforms. For each point, we are given (possibly noisy) measurements of its local coordinates in some of the coordinate systems. Alternatively, for each coordinate system, we observe the coordinates of a subset of the points. The problem of estimating the global coordinates of the N points (up to a rigid transform) from such measurements comes up in distributed approaches to molecular conformation and sensor network localization, and also in computer vision and graphics. The least-squares formulation of this problem, although nonconvex, has a well-known closed-form solution when M = 2 (based on the singular value decomposition (SVD)). However, no closed-form solution is known for M >= 3. In this paper, we demonstrate how the least-squares formulation can be relaxed into a convex program, namely, a semidefinite program (SDP). By setting up connections between the uniqueness of this SDP and results from rigidity theory, we prove conditions for exact and stable recovery for the SDP relaxation. In particular, we prove that the SDP relaxation can guarantee recovery under more adversarial conditions compared to earlier proposed spectral relaxations, and we derive error bounds for the registration error incurred by the SDP relaxation. We also present results of numerical experiments on simulated data to confirm the theoretical findings. We empirically demonstrate that (a) unlike the spectral relaxation, the relaxation gap is mostly zero for the SDP (i.e., we are able to solve the original nonconvex least-squares problem) up to a certain noise threshold, and (b) the SDP performs significantly better than spectral and manifold-optimization methods, particularly at large noise levels.

Characterization of friction at three contact pairs by photoelastic Isotropic point (IP)

Friction coefficient between a circular-disk periphery and V-block surface was determined by introducing the concept of isotropic point (IP) in isochromatic field of the disk under three-point symmetric loading. IP position on the symmetry axis depends on active coefficient of friction during experiment. We extend this work to asymmetric loading of circular disk in which case two frictional contact pairs out of three loading contacts, independently control the unconstrained IP location. Photoelastic experiment is conducted on particular case of asymmetric three-point loading of circular disk. Basics of digital image processing are used to extract few essential parameters from experimental image, particularly IP location. Analytical solution by Flamant for half plane with a concentrated load, is utilized to derive stress components for required loading configurations of the disk. IP is observed, in analytical simulations of three-point asymmetric normal loading, to move from vertical axis to the boundary along an ellipse-like curve. When friction is included in the analysis, IP approaches the center with increase in loading friction and it goes away with increase in support friction. With all these insights, using experimental IP information, friction angles at three contact pairs of circular disk under asymmetric loading, are determined.

Direct measurements of growing amorphous order and non-monotonic dynamic correlations in a colloidal glass-former

The transformation of flowing liquids into rigid glasses is thought to involve increasingly cooperative relaxation dynamics as the temperature approaches that of the glass transition. However, the precise nature of this motion is unclear, and a complete understanding of vitrification thus remains elusive. Of the numerous theoretical perspectives(1-4) devised to explain the process, random first-order theory (RFOT; refs 2,5) is a well-developed thermodynamic approach, which predicts a change in the shape of relaxing regions as the temperature is lowered. However, the existence of an underlying `ideal' glass transition predicted by RFOT remains debatable, largely because the key microscopic predictions concerning the growth of amorphous order and the nature of dynamic correlations lack experimental verification. Here, using holographic optical tweezers, we freeze a wall of particles in a two-dimensional colloidal glass-forming liquid and provide direct evidence for growing amorphous order in the form of a static point-to-set length. We uncover the non-monotonic dependence of dynamic correlations on area fraction and show that this non-monotonicity follows directly from the change in morphology and internal structure of cooperatively rearranging regions(6,7). Our findings support RFOT and thereby constitute a crucial step in distinguishing between competing theories of glass formation.

Independent Positioning of Magnetic Nanomotors

There is considerable interest in powering and maneuvering nanostructures remotely in fluidic media using noninvasive fuel-free methods, for which small homogeneous magnetic fields are ideally suited. Current strategies include helical propulsion of chiral nanostructures, cilia-like motion of flexible filaments, and surface assisted translation of asymmetric colloidal doublets and magnetic nanorods, in all of which the individual structures are moved in a particular direction that is completely tied to the characteristics of the driving fields. As we show in this paper, when we use appropriate magnetic field configurations and actuation time scales, it is possible to maneuver geometrically identical nanostructures in different directions, and subsequently position them at arbitrary locations with respect to each other. The method reported here requires proximity of the nanomotors to a solid surface, and could be useful in applications that require remote and independent control over individual components in microfluidic environments.

A comparative study of failure features in aerospace grade unidirectional and bidirectional woven CFRP composite laminates under four-point bend fatigue loads

Damage mechanisms in unidirectional (UD) and bi-directional (BD) woven carbon fiber reinforced polymer (CFRP) laminates subjected to four point flexure, both in static and fatigue loadings, were studied. The damage progression in composites was monitored by observing the slopes of the load vs. deflection data that represent the stiffness of the given specimen geometry over a number of cycles. It was observed that the unidirectional composites exhibit gradual loss in stiffness whereas the bidirectional woven composites show a relatively quicker loss during stage II of fatigue damage progression. Both, the static and the fatigue failures in unidirectional carbon fiber reinforced polymer composites originates due to generation of cracks on compression face while in bidirectional woven composites the damage ensues from both the compression and the tensile faces. These observations are supported by a detailed fractographic analysis.

De-DUFing the DUFs: Deciphering distant evolutionary relationships of Domains of Unknown Function using sensitive homology detection methods

Background: In the post-genomic era where sequences are being determined at a rapid rate, we are highly reliant on computational methods for their tentative biochemical characterization. The Pfam database currently contains 3,786 families corresponding to ``Domains of Unknown Function'' (DUF) or ``Uncharacterized Protein Family'' (UPF), of which 3,087 families have no reported three-dimensional structure, constituting almost one-fourth of the known protein families in search for both structure and function. Results: We applied a `computational structural genomics' approach using five state-of-the-art remote similarity detection methods to detect the relationship between uncharacterized DUFs and domain families of known structures. The association with a structural domain family could serve as a start point in elucidating the function of a DUF. Amongst these five methods, searches in SCOP-NrichD database have been applied for the first time. Predictions were classified into high, medium and low-confidence based on the consensus of results from various approaches and also annotated with enzyme and Gene ontology terms. 614 uncharacterized DUFs could be associated with a known structural domain, of which high confidence predictions, involving at least four methods, were made for 54 families. These structure-function relationships for the 614 DUF families can be accessed on-line at http://proline.biochem.iisc.ernet.in/RHD_DUFS/. For potential enzymes in this set, we assessed their compatibility with the associated fold and performed detailed structural and functional annotation by examining alignments and extent of conservation of functional residues. Detailed discussion is provided for interesting assignments for DUF3050, DUF1636, DUF1572, DUF2092 and DUF659. Conclusions: This study provides insights into the structure and potential function for nearly 20 % of the DUFs. Use of different computational approaches enables us to reliably recognize distant relationships, especially when they converge to a common assignment because the methods are often complementary. We observe that while pointers to the structural domain can offer the right clues to the function of a protein, recognition of its precise functional role is still `non-trivial' with many DUF domains conserving only some of the critical residues. It is not clear whether these are functional vestiges or instances involving alternate substrates and interacting partners. Reviewers: This article was reviewed by Drs Eugene Koonin, Frank Eisenhaber and Srikrishna Subramanian.