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.

Radial infall of two compact objects: 2.5-post-Newtonian linear momentum flux and associated recoil

The loss rate of linear momentum from a binary system composed of compact objects (radially falling towards each other under mutual gravitational influence) has been investigated using the multipolar post-Minkowskian approach. The 2.5PN accurate analytical formula for the linear momentum flux is provided, in terms of the separation of the two objects, in harmonic coordinates, both for a finite and an infinite initial separation. The 2.5PN formulas for the linear momentum flux are finally used to estimate the recoil velocity accumulated during a premerger phase of the binary evolution.

Piecewise Linearization Technique for Compact Charge Modeling of Independent DG MOSFET

Charge linearization techniques have been used over the years in advanced compact models for bulk and double-gate MOSFETs in order to approximate the position along the channel as a quadratic function of the surface potential (or inversion charge densities) so that the terminal charges can be expressed as a compact closed-form function of source and drain end surface potentials (or inversion charge densities). In this paper, in case of the independent double-gate MOSFETs, we show that the same technique could be used to model the terminal charges quite accurately only when the 1-D Poisson solution along the channel is fully hyperbolic in nature or the effective gate voltages are same. However, for other bias conditions, it leads to significant error in terminal charge computation. We further demonstrate that the amount of nonlinearity that prevails between the surface potentials along the channel actually dictates if the conventional charge linearization technique could be applied for a particular bias condition or not. Taking into account this nonlinearity, we propose a compact charge model, which is based on a novel piecewise linearization technique and shows excellent agreement with numerical and Technology Computer-Aided Design (TCAD) simulations for all bias conditions and also preserves the source/drain symmetry which is essential for Radio Frequency (RF) circuit design. The model is implemented in a professional circuit simulator through Verilog-A, and simulation examples for different circuits verify good model convergence.

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.

Inclusion of body doping in compact models for fully-depleted common double gate MOSFET adapted to gate-oxide thickness asymmetry

Since it is difficult to find the analytical solution of the governing Poisson equation for double gate MOSFETs with the body doping term included, the majority of the compact models are developed for undoped-body devices for which the analytical solution is available. Proposed is a simple technique to included a body doping term in such surface potential based common double gate MOSFET models also by taking into account any differences between the gate oxide thickness. The proposed technique is validated against TCAD simulation and found to be accurate as long as the channel is fully depleted.

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.

A Compact and Compliant External Pipe-Crawling Robot

The focus of this paper is on the practical aspects of design, prototyping, and testing of a compact, compliant external pipe-crawling robot that can inspect a closely spaced bundle of pipes in hazardous environments and areas that are inaccessible to humans. The robot consists of two radially deployable compliant ring actuators that are attached to each other along the longitudinal axis of the pipe by a bidirectional linear actuator. The robot imitates the motion of an inchworm. The novel aspect of the compliant ring actuator is a spring-steel compliant mechanism that converts circumferential motion to radial motion of its multiple gripping pads. Circumferential motion to ring actuators is provided by two shape memory alloy (SMA) wires that are guided by insulating rollers. The design of the compliant mechanism is derived from a radially deployable mechanism. A unique feature of the design is that the compliant mechanism provides the necessary kinematic function within the limited annular space around the pipe and serves as the bias spring for the SMA wires. The robot has a control circuit that sequentially activates the SMA wires and the linear actuator; it also controls the crawling speed. The robot has been fabricated, tested, and automated. Its crawling speed is about 45 mm/min, and the weight is about 150 g. It fits within an annular space of a radial span of 15 mm to crawl on a pipe of 60-mm outer diameter.

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.

Mixing enhancement in a compact trapped vortex combustor

Previous studies on a single-cavity, compact trapped vortex combustor concept showed good flame stability for a wide range of flow conditions. However, achieving good mixing between cavity products and mainstream flow was still a major challenge. In the present study, a passive mixing enhancement strategy of using inclined struts along with a flow guide vane is presented and experimentally tested at atmospheric pressure conditions. Results show excellent mixing and consequently low values of the combustor exit pattern factor in the range of 0.1 and small flame lengths (57 times the main-duct depth). The pressure drop is small in the range of 0.35%, and NOx levels of the order of 12ppm are achieved. The flame stability is excellent, and combustion efficiency is reasonable in the range of 96%. The effectiveness of the proposed strategy is explained on the basis of in-situ OH chemiluminescence images and prior numerical simulations of the resulting complex flow field. The flow guide vane is observed to lead to a counterclockwise cavity vortex, which is conducive to the rise of cavity combustion products along the inclined struts and subsequent mixing with the mainstream flow.

Exponential compact higher order scheme and their stability analysis for unsteady convection-diffusion equations

Exponential compact higher-order schemes have been developed for unsteady convection-diffusion equation (CDE). One of the developed scheme is sixth-order accurate which is conditionally stable for the Peclet number 0 <= Pe <= 2.8 and the other is fourth-order accurate which is unconditionally stable. Schemes for two-dimensional (2D) problems are made to use alternate direction implicit (ADI) algorithm. Example problems are solved and the numerical solutions are compared with the analytical solutions for each case.

Compact polarization dependent EBG surface with fractal boundary patches

Patches with variants of fractal Minkowski curves as boundaries are used here to design a polarization dependent electromagnetic bandgap surface. Reflection phases of the proposed structure depends upon the polarization state of the incident wave and frequency. The phase difference between the x-polarized and y-polarized components of the reflected wave can be as high as 200 degrees and this is achieved without excessive increase in unit cell dimensions and vias. The performance of the surface is analyzed numerically using CST microwave studio. The potential applications of the surface are in polarization conversion surfaces, polarimetric radar calibration, and RCS reduction.