Comments on Identification of Totally Symmetric Boolean Functions

A modification in the algorithm for the detection of totally symmetric functions as expounded by the author in an earlier note1 is presented here. The modified algorithm takes care of a limited number of functions that escape detection by the previous method.

An Algorithm for Testing 2-Asummability of Boolean Functions

Simple algorithms have been developed to generate pairs of minterms forming a given 2-sum and thereby to test 2-asummability of switching functions. The 2-asummability testing procedure can be easily implemented on the computer. Since 2-asummability is a necessary and sufficient condition for a switching function of upto eight variables to be linearly separable (LS), it can be used for testing LS switching functions of upto eight variables.

Lower bounds for testing triangle-freeness in Boolean functions

Given a Boolean function , we say a triple (x, y, x + y) is a triangle in f if . A triangle-free function contains no triangle. If f differs from every triangle-free function on at least points, then f is said to be -far from triangle-free. In this work, we analyze the query complexity of testers that, with constant probability, distinguish triangle-free functions from those -far from triangle-free. Let the canonical tester for triangle-freeness denotes the algorithm that repeatedly picks x and y uniformly and independently at random from , queries f(x), f(y) and f(x + y), and checks whether f(x) = f(y) = f(x + y) = 1. Green showed that the canonical tester rejects functions -far from triangle-free with constant probability if its query complexity is a tower of 2's whose height is polynomial in . Fox later improved the height of the tower in Green's upper bound to . A trivial lower bound of on the query complexity is immediate. In this paper, we give the first non-trivial lower bound for the number of queries needed. We show that, for every small enough , there exists an integer such that for all there exists a function depending on all n variables which is -far from being triangle-free and requires queries for the canonical tester. We also show that the query complexity of any general (possibly adaptive) one-sided tester for triangle-freeness is at least square root of the query complexity of the corresponding canonical tester. Consequently, this means that any one-sided tester for triangle-freeness must make at least queries.

An algorithm to detect linearly separable clusters of binary patterns

The clusters of binary patterns can be considered as Boolean functions of the (binary) features. Such a relationship between the linearly separable (LS) Boolean functions and LS clusters of binary patterns is examined. An algorithm is presented to answer the questions of the type: “Is the cluster formed by the subsets of the (binary) data set having certain features AND/NOT having certain other features, LS from the remaining set?” The algorithm uses the sequences of Numbered Binary Form (NBF) notation and some elementary (NPN) transformations of the binary data.

An algorithm to detect linearly separable clusters of binary patterns

The clusters of binary patterns can be considered as Boolean functions of the (binary) features. Such a relationship between the linearly separable (LS) Boolean functions and LS clusters of binary patterns is examined. An algorithm is presented to answer the questions of the type: “Is the cluster formed by the subsets of the (binary) data set having certain features AND/NOT having certain other features, LS from the remaining set?” The algorithm uses the sequences of Numbered Binary Form (NBF) notation and some elementary (NPN) transformations of the binary data.

Lossless and lossy image compression using Boolean function minimization

A novel approach for lossless as well as lossy compression of monochrome images using Boolean minimization is proposed. The image is split into bit planes. Each bit plane is divided into windows or blocks of variable size. Each block is transformed into a Boolean switching function in cubical form, treating the pixel values as output of the function. Compression is performed by minimizing these switching functions using ESPRESSO, a cube based two level function minimizer. The minimized cubes are encoded using a code set which satisfies the prefix property. Our technique of lossless compression involves linear prediction as a preprocessing step and has compression ratio comparable to that of JPEG lossless compression technique. Our lossy compression technique involves reducing the number of bit planes as a preprocessing step which incurs minimal loss in the information of the image. The bit planes that remain after preprocessing are compressed using our lossless compression technique based on Boolean minimization. Qualitatively one cannot visually distinguish between the original image and the lossy image and the value of mean square error is kept low. For mean square error value close to that of JPEG lossy compression technique, our method gives better compression ratio. The compression scheme is relatively slower while the decompression time is comparable to that of JPEG.

Finite volume evolution Galerkin method for hyperbolic conservation laws with spatially varying flux functions

We present a generalization of the finite volume evolution Galerkin scheme [M. Lukacova-Medvid'ova,J. Saibertov'a, G. Warnecke, Finite volume evolution Galerkin methods for nonlinear hyperbolic systems, J. Comp. Phys. (2002) 183 533-562; M. Luacova-Medvid'ova, K.W. Morton, G. Warnecke, Finite volume evolution Galerkin (FVEG) methods for hyperbolic problems, SIAM J. Sci. Comput. (2004) 26 1-30] for hyperbolic systems with spatially varying flux functions. Our goal is to develop a genuinely multi-dimensional numerical scheme for wave propagation problems in a heterogeneous media. We illustrate our methodology for acoustic waves in a heterogeneous medium but the results can be generalized to more complex systems. The finite volume evolution Galerkin (FVEG) method is a predictor-corrector method combining the finite volume corrector step with the evolutionary predictor step. In order to evolve fluxes along the cell interfaces we use multi-dimensional approximate evolution operator. The latter is constructed using the theory of bicharacteristics under the assumption of spatially dependent wave speeds. To approximate heterogeneous medium a staggered grid approach is used. Several numerical experiments for wave propagation with continuous as well as discontinuous wave speeds confirm the robustness and reliability of the new FVEG scheme.

Dynamics of a dilute sheared inelastic fluid. I. Hydrodynamic modes and velocity correlation functions

The hydrodynamic modes and the velocity autocorrelation functions for a dilute sheared inelastic fluid are analyzed using an expansion in the parameter epsilon=(1-e)(1/2), where e is the coefficient of restitution. It is shown that the hydrodynamic modes for a sheared inelastic fluid are very different from those for an elastic fluid in the long-wave limit, since energy is not a conserved variable when the wavelength of perturbations is larger than the ``conduction length.'' In an inelastic fluid under shear, there are three coupled modes, the mass and the momenta in the plane of shear, which have a decay rate proportional to k(2/3) in the limit k -> 0, if the wave vector has a component along the flow direction. When the wave vector is aligned along the gradient-vorticity plane, we find that the scaling of the growth rate is similar to that for an elastic fluid. The Fourier transforms of the velocity autocorrelation functions are calculated for a steady shear flow correct to leading order in an expansion in epsilon. The time dependence of the autocorrelation function in the long-time limit is obtained by estimating the integral of the Fourier transform over wave number space. It is found that the autocorrelation functions for the velocity in the flow and gradient directions decay proportional to t(-5/2) in two dimensions and t(-15/4) in three dimensions. In the vorticity direction, the decay of the autocorrelation function is proportional to t(-3) in two dimensions and t(-7/2) in three dimensions.

Hybrid stiff-string-polynomial basis functions for vibration analysis of high speed rotating beams

A new finite element is developed for free vibration analysis of high speed rotating beams using basis functions which use a linear combination of the solution of the governing static differential equation of a stiff-string and a cubic polynomial. These new shape functions depend on rotation speed and element position along the beam and account for the centrifugal stiffening effect. The natural frequencies predicted by the proposed element are compared with an element with stiff-string, cubic polynomial and quintic polynomial shape functions. It is found that the new element exhibits superior convergence compared to the other basis functions.

The Parallel Complexity Of Propagation In Boolean Circuits

We consider the problem of deciding whether the output of a boolean circuit is determined by a partial assignment to its inputs. This problem is easily shown to be hard, i.e., co-Image Image -complete. However, many of the consequences of a partial input assignment may be determined in linear time, by iterating the following step: if we know the values of some inputs to a gate, we can deduce the values of some outputs of that gate. This process of iteratively deducing some of the consequences of a partial assignment is called propagation. This paper explores the parallel complexity of propagation, i.e., the complexity of determining whether the output of a given boolean circuit is determined by propagating a given partial input assignment. We give a complete classification of the problem into those cases that are Image -complete and those that are unlikely to be Image complete.

Deep inelastic electroproduction structure functions for polarized and unpolarized proton targets

Following Ioffe's method of QCD sum rules the structure functions F2(x) for deep inelastic ep and en scattering are calculated. Valence u-quark and d-quark distributions are obtained in the range 0.1 less, approximate x <0.4 and compared with data. In the case of polarized targets the structure function g1(x) and the asymmetry Image Full-size image are calculated. The latter is in satisfactory agreement in sign and magnitude with experiments for x in the range 0.1< x < 0.4.

Do H-functions always increase during Violent Relaxation

Recent work on the violent relaxation of collisionless stellar systems has been based on the notion of a wide class of entropy functions. A theorem concerning entropy increase has been proved. We draw attention to some underlying assumptions that have been ignored in the applications of this theorem to stellar dynamical problems. Once these are taken into account, the use of this theorem is at best heuristic. We present a simple counter-example.

Testing threshold functions using implied minterm structure

A geometrical structure called the implied minterm structure (IMS) has been developed from the properties of minterms of a threshold function. The IMS is useful for the manual testing of linear separability of switching functions of up to six variables. This testing is done just by inspection of the plot of the function on the IMS.

Transmission loss analysis of rectangular expansion chamber with arbitrary location of inlet/outlet by means of Green's functions

Transmission loss of a rectangular expansion chamber, the inlet and outlet of which are situated at arbitrary locations of the chamber, i.e., the side wall or the face of the chamber, are analyzed here based on the Green's function of a rectangular cavity with homogeneous boundary conditions. The rectangular chamber Green's function is expressed in terms of a finite number of rigid rectangular cavity mode shapes. The inlet and outlet ports are modeled as uniform velocity pistons. If the size of the piston is small compared to wavelength, then the plane wave excitation is a valid assumption. The velocity potential inside the chamber is expressed by superimposing the velocity potentials of two different configurations. The first configuration is a piston source at the inlet port and a rigid termination at the outlet, and the second one is a piston at the outlet with a rigid termination at the inlet. Pressure inside the chamber is derived from velocity potentials using linear momentum equation. The average pressure acting on the pistons at the inlet and outlet locations is estimated by integrating the acoustic pressure over the piston area in the two constituent configurations. The transfer matrix is derived from the average pressure values and thence the transmission loss is calculated. The results are verified against those in the literature where use has been made of modal expansions and also numerical models (FEM fluid). The transfer matrix formulation for yielding wall rectangular chambers has been derived incorporating the structural–acoustic coupling. Parametric studies are conducted for different inlet and outlet configurations, and the various phenomena occurring in the TL curves that cannot be explained by the classical plane wave theory, are discussed.

Learning Optimal Discriminant Functions through a Cooperative Game of Automata

The problem of learning correct decision rules to minimize the probability of misclassification is a long-standing problem of supervised learning in pattern recognition. The problem of learning such optimal discriminant functions is considered for the class of problems where the statistical properties of the pattern classes are completely unknown. The problem is posed as a game with common payoff played by a team of mutually cooperating learning automata. This essentially results in a probabilistic search through the space of classifiers. The approach is inherently capable of learning discriminant functions that are nonlinear in their parameters also. A learning algorithm is presented for the team and convergence is established. It is proved that the team can obtain the optimal classifier to an arbitrary approximation. Simulation results with a few examples are presented where the team learns the optimal classifier.