A computational algorithm for the verification of tautologies in propositional calculus

A computational algorithm (based on Smullyan's analytic tableau method) that varifies whether a given well-formed formula in propositional calculus is a tautology or not has been implemented on a DEC system 10. The stepwise refinement approch of program development used for this implementation forms the subject matter of this paper. The top-down design has resulted in a modular and reliable program package. This computational algoritlhm compares favourably with the algorithm based on the well-known resolution principle used in theorem provers.

Estimation of Probabilistic Bounds on Phase CPI and Relevance in WCET Analysis

Estimating program worst case execution time(WCET) accurately and efficiently is a challenging task. Several programs exhibit phase behavior wherein cycles per instruction (CPI) varies in phases during execution. Recent work has suggested the use of phases in such programs to estimate WCET with minimal instrumentation. However the suggested model uses a function of mean CPI that has no probabilistic guarantees. We propose to use Chebyshev's inequality that can be applied to any arbitrary distribution of CPI samples, to probabilistically bound CPI of a phase. Applying Chebyshev's inequality to phases that exhibit high CPI variation leads to pessimistic upper bounds. We propose a mechanism that refines such phases into sub-phases based on program counter(PC) signatures collected using profiling and also allows the user to control variance of CPI within a sub-phase. We describe a WCET analyzer built on these lines and evaluate it with standard WCET and embedded benchmark suites on two different architectures for three chosen probabilities, p={0.9, 0.95 and 0.99}. For p= 0.99, refinement based on PC signatures alone, reduces average pessimism of WCET estimate by 36%(77%) on Arch1 (Arch2). Compared to Chronos, an open source static WCET analyzer, the average improvement in estimates obtained by refinement is 5%(125%) on Arch1 (Arch2). On limiting variance of CPI within a sub-phase to {50%, 10%, 5% and 1%} of its original value, average accuracy of WCET estimate improves further to {9%, 11%, 12% and 13%} respectively, on Arch1. On Arch2, average accuracy of WCET improves to 159% when CPI variance is limited to 50% of its original value and improvement is marginal beyond that point.

Probabilistic seismic hazard analysis for Bangalore

This article presents the results of probabilistic seismic hazard analysis (PSHA) for Bangalore, South India. Analyses have been carried out considering the seismotectonic parameters of the region covering a radius of 350 km keeping Bangalore as the center. Seismic hazard parameter `b' has been evaluated considering the available earthquake data using (1) Gutenberg-Richter (G-R) relationship and (2) Kijko and Sellevoll (1989, 1992) method utilizing extreme and complete catalogs. The `b' parameter was estimated to be 0.62 to 0.98 from G-R relation and 0.87 +/- A 0.03 from Kijko and Sellevoll method. The results obtained are a little higher than the `b' values published earlier for southern India. Further, probabilistic seismic hazard analysis for Bangalore region has been carried out considering six seismogenic sources. From the analysis, mean annual rate of exceedance and cumulative probability hazard curve for peak ground acceleration (PGA) and spectral acceleration (Sa) have been generated. The quantified hazard values in terms of the rock level peak ground acceleration (PGA) are mapped for 10% probability of exceedance in 50 years on a grid size of 0.5 km x 0.5 km. In addition, Uniform Hazard Response Spectrum (UHRS) at rock level is also developed for the 5% damping corresponding to 10% probability of exceedance in 50 years. The peak ground acceleration (PGA) value of 0.121 g obtained from the present investigation is slightly lower (but comparable) than the PGA values obtained from the deterministic seismic hazard analysis (DSHA) for the same area. However, the PGA value obtained in the current investigation is higher than PGA values reported in the global seismic hazard assessment program (GSHAP) maps of Bhatia et al. (1999) for the shield area.

Solution of a System of Generalized Abel Integral Equations Using Fractional Calculus

A method is presented for obtaining useful closed form solution of a system of generalized Abel integral equations by using the ideas of fractional integral operators and their applications. This system appears in solving certain mixed boundary value problems arising in the classical theory of elasticity.

High-resolution refinement of orthorhombic bovine pancreatic phospholipase A2

The X-ray structure of recombinant bovine pancreatic phospholipase A(2) (PLA2), which specifically catalyzes the cleavage of the sn-2 acylester bond of phospholipids, has been refined at 1.5 Angstrom resolution. The crystal belongs to the space group P2(1)2(1)2(1) with unit-cell parameters a = 47.12, b = 64.59 and c = 38.14 Angstrom similar to the native enzyme reported previously by Dijkstra et nl. [J. Mel. Biol. (1981), 147, 97-123]. The refinement converged to an R value of 18.4% (R-free = 22.8%) for 16 374 reflections between 10.0 and 1.5 Angstrom resolution. The surface-loop residues (60-70) art: ordered in the present orthorhombic recombinant enzyme, but disordered in the trigonal recombinant enzyme. The active-site residues, His48, Asp99, and the catalytic water superimpose well with the trigonal form. Besides the catalytic water which is hydrogen bonded to His48, it is often seen that there is a second water attached to the same N atom of His48 and simultaneously hydrogen bonded to the O atom of Asp49. It is thought that the second water facilitates the tautomerism of His48 for enzyme catalysis, The catalytic water is also hydrogen bonded to the equatorial water coordinated to the calcium ion, In addition to the equatorial water, there is also an axial calcium water and the additional structural water. These five common water molecules are hydrogen bonded to the additional 16 water molecules in the present orthorhombic structure which may further enhance the structural integrity of the active site. Besides the protein and one calcium ion, a total of 134 water molecules were located in the present high-resolution refinement.

A probabilistic constrained nonlinear optimization framework to optimize RED parameters

The random early detection (RED) technique has seen a lot of research over the years. However, the functional relationship between RED performance and its parameters viz,, queue weight (omega(q)), marking probability (max(p)), minimum threshold (min(th)) and maximum threshold (max(th)) is not analytically availa ble. In this paper, we formulate a probabilistic constrained optimization problem by assuming a nonlinear relationship between the RED average queue length and its parameters. This problem involves all the RED parameters as the variables of the optimization problem. We use the barrier and the penalty function approaches for its Solution. However (as above), the exact functional relationship between the barrier and penalty objective functions and the optimization variable is not known, but noisy samples of these are available for different parameter values. Thus, for obtaining the gradient and Hessian of the objective, we use certain recently developed simultaneous perturbation stochastic approximation (SPSA) based estimates of these. We propose two four-timescale stochastic approximation algorithms based oil certain modified second-order SPSA updates for finding the optimum RED parameters. We present the results of detailed simulation experiments conducted over different network topologies and network/traffic conditions/settings, comparing the performance of Our algorithms with variants of RED and a few other well known adaptive queue management (AQM) techniques discussed in the literature.

Refinement of defection strategies stabilizes cooperation

Cooperation among unrelated individuals is an enduring evolutionary riddle and a number of possible solutions have been suggested. Most of these suggestions attempt to refine cooperative strategies, while little attention is given to the fact that novel defection strategies can also evolve in the population. Especially in the presence of punishment to the defectors and public knowledge of strategies employed by the players, a defecting strategy that avoids getting punished by selectively cooperating only with the punishers can get a selective benefit over non-conditional defectors. Furthermore, if punishment ensures cooperation from such discriminating defectors, defectors who punish other defectors can evolve as well. We show that such discriminating and punishing defectors can evolve in the population by natural selection in a Prisoner’s Dilemma game scenario, even if discrimination is a costly act. These refined defection strategies destabilize unconditional defectors. They themselves are, however, unstable in the population. Discriminating defectors give selective benefit to the punishers in the presence of non-punishers by cooperating with them and defecting with others. However, since these players also defect with other discriminators they suffer fitness loss in the pure population. Among the punishers, punishing cooperators always benefit in contrast to the punishing defectors, as the latter not only defect with other punishing defectors but also punish them and get punished. As a consequence of both these scenarios, punishing cooperators get stabilized in the population. We thus show ironically that refined defection strategies stabilize cooperation. Furthermore, cooperation stabilized by such defectors can work under a wide range of initial conditions and is robust to mistakes.

Site classification and estimation of surface level seismic hazard using geophysical data and probabilistic approach

This paper presents the site classification of Bangalore Mahanagar Palike (BMP) area using geophysical data and the evaluation of spectral acceleration at ground level using probabilistic approach. Site classification has been carried out using experimental data from the shallow geophysical method of Multichannel Analysis of Surface wave (MASW). One-dimensional (1-D) MASW survey has been carried out at 58 locations and respective velocity profiles are obtained. The average shear wave velocity for 30 m depth (Vs(30)) has been calculated and is used for the site classification of the BMP area as per NEHRP (National Earthquake Hazards Reduction Program). Based on the Vs(30) values major part of the BMP area can be classified as ``site class D'', and ``site class C'. A smaller portion of the study area, in and around Lalbagh Park, is classified as ``site class B''. Further, probabilistic seismic hazard analysis has been carried out to map the seismic hazard in terms spectral acceleration (S-a) at rock and the ground level considering the site classes and six seismogenic sources identified. The mean annual rate of exceedance and cumulative probability hazard curve for S. have been generated. The quantified hazard values in terms of spectral acceleration for short period and long period are mapped for rock, site class C and D with 10% probability of exceedance in 50 years on a grid size of 0.5 km. In addition to this, the Uniform Hazard Response Spectrum (UHRS) at surface level has been developed for the 5% damping and 10% probability of exceedance in 50 years for rock, site class C and D These spectral acceleration and uniform hazard spectrums can be used to assess the design force for important structures and also to develop the design spectrum.

Estimation of peak ground acceleration and spectral acceleration for South India with local site effects: probabilistic approach

In this work an attempt has been made to evaluate the seismic hazard of South India (8.0 degrees N-20 degrees N; 72 degrees E-88 degrees E) based on the probabilistic seismic hazard analysis (PSHA). The earthquake data obtained from different sources were declustered to remove the dependent events. A total of 598 earthquakes of moment magnitude 4 and above were obtained from the study area after declustering, and were considered for further hazard analysis. The seismotectonic map of the study area was prepared by considering the faults, lineaments and the shear zones in the study area which are associated with earthquakes of magnitude 4 and above. For assessing theseismic hazard, the study area was divided into small grids of size 0.1 degrees x0.1 degrees, and the hazard parameters were calculated at the centre of each of these grid cells by considering all the seismic sources with in a radius of 300 km. Rock level peak horizontal acceleration (PHA) and spectral acceleration (SA) values at 1 corresponding to 10% and 2% probability of exceedance in 50 years have been calculated for all the grid points. The contour maps showing the spatial variation of these values are presented here. Uniform hazard response spectrum (UHRS) at rock level for 5% damping and 10% and 2% probability of exceedance in 50 years were also developed for all the grid points. The peak ground acceleration (PGA) at surface level was calculated for the entire South India for four different site classes. These values can be used to find the PGA values at any site in South India based on site class at that location. Thus, this method can be viewed as a simplified method to evaluate the PGA values at any site in the study area.

Probabilistic Seismic Design of Pile Foundations in Non Liquefiable Soil by Response Spectrum Approach

The behavior of pile foundations in non liquefiable soil under seismic loading is considerably influenced by the variability in the soil and seismic design parameters. Hence, probabilistic models for the assessment of seismic pile design are necessary. Deformation of pile foundation in non liquefiable soil is dominated by inertial force from superstructure. The present study considers a pseudo-static approach based on code specified design response spectra. The response of the pile is determined by equivalent cantilever approach. The soil medium is modeled as a one-dimensional random field along the depth. The variability associated with undrained shear strength, design response spectrum ordinate, and superstructure mass is taken into consideration. Monte Carlo simulation technique is adopted to determine the probability of failure and reliability indices based on pile failure modes, namely exceedance of lateral displacement limit and moment capacity. A reliability-based design approach for the free head pile under seismic force is suggested that enables a rational choice of pile design parameters.

An interpreter for slips-An applicative language based on LAMBDA-Calculus

An applicative language based on the LAMBDA-Calculus is presented. The language, SLIPS (Small Language for Instruction Purposes), is described using the LAMBDA-Calculus as a metalanguage. A call-by-need mechanism of function invocation eliminates the drawbacks of both call-by-name and call-by-value. The system has been implemented in PASCAL.

On the Fourier refinement of protein structures

The situation normally encountered in the high-resolution refinement of protein structures is one in which the inaccurate positions of P out of a total of N atoms are known whereas those of the remaining atoms are unknown. Fourier maps with coefficients (FN -- F'P) × exp (i[alpha]'P) and (mFN -- nF'P) exp (i[alpha]'P), where FN is the observed structure factor and F'P and [alpha]'P are the magnitude and the phase angle of the calculated structure factor corresponding to the inaccurate atomic positions, are often used to correct the positions of the P atoms and to determine those of the Q unknown atoms. A general theoretical approach is presented to elucidate the effect of errors in the positions of the known atoms on the corrected positions of the known atoms and the positions of the unknown atoms derived from such maps. The theory also leads to the optimal choice of parameters used in the different syntheses. When the errors in the positions of the input atoms are systematic, their effects are not taken care of automatically by the syntheses.

A probabilistic approach to the problem of electron localization in disordered systems and sharpness of the mobility edge

By applying the theory of the asymptotic distribution of extremes and a certain stability criterion to the question of the domain of convergence in the probability sense, of the renormalized perturbation expansion (RPE) for the site self-energy in a cellularly disordered system, an expression has been obtained in closed form for the probability of nonconvergence of the RPE on the real-energy axis. Hence, the intrinsic mobility mu (E) as a function of the carrier energy E is deduced to be given by mu (E)= mu 0exp(-exp( mod E mod -Ec) Delta ), where Ec is a nominal 'mobility edge' and Delta is the width of the random site-energy distribution. Thus mobility falls off sharply but continuously for mod E mod >Ec, in contradistinction with the notion of an abrupt 'mobility edge' proposed by Cohen et al. and Mott. Also, the calculated electrical conductivity shows a temperature dependence in qualitative agreement with experiments on disordered semiconductors.

Local structure in LaMnO3 and CaMnO3 perovskites: A quantitative structural refinement of mn K-edge XANES data

Hole-doped perovskites such as La1-xCaxMnO3 present special magnetic and magnetotransport properties, and it is commonly accepted that the local atomic structure around Mn ions plays a crucial role in determining these peculiar features. Therefore experimental techniques directly probing the local atomic structure, like x-ray absorption spectroscopy (XAS), have been widely exploited to deeply understand the physics of these compounds. Quantitative XAS analysis usually concerns the extended region [extended x-ray absorption fine structure (EXAFS)] of the absorption spectra. The near-edge region [x-ray absorption near-edge spectroscopy (XANES)] of XAS spectra can provide detailed complementary information on the electronic structure and local atomic topology around the absorber. However, the complexity of the XANES analysis usually prevents a quantitative understanding of the data. This work exploits the recently developed MXAN code to achieve a quantitative structural refinement of the Mn K-edge XANES of LaMnO3 and CaMnO3 compounds; they are the end compounds of the doped manganite series LaxCa1-xMnO3. The results derived from the EXAFS and XANES analyses are in good agreement, demonstrating that a quantitative picture of the local structure can be obtained from XANES in these crystalline compounds. Moreover, the quantitative XANES analysis provides topological information not directly achievable from EXAFS data analysis. This work demonstrates that combining the analysis of extended and near-edge regions of Mn K-edge XAS spectra could provide a complete and accurate description of Mn local atomic environment in these compounds.

Confirmation of linkage and refinement of the RP28 locus for autosomal recessive retinitis pigmentosa on chromosome 2p14-p15 in an Indian family

PURPOSE: To report the linkage analysis of retinitis pigmentosa (RP) in an Indian family. METHODS: Individuals were examined for symptoms of retinitis pigmentosa and their blood samples were withdrawn for genetic analysis. The disorder was tested for linkage to known 14 adRP and 22 arRP loci using microsatellite markers. RESULTS: Seventeen individuals including seven affecteds participated in the study. All affected individuals had typical RP. The age of onset of the disease ranged from 8-18 years. The disorder in this family segregated either as an autosomal recessive trait with pseudodominance or an autosomal dominant trait. Linkage to an autosomal recessive locus RP28 on chromosome 2p14-p15 was positive with a maximum two-point lod score of 3.96 at theta=0 for D2S380. All affected individuals were homozygous for alleles at D2S2320, D2S2397, D2S380, and D2S136. Recombination events placed the minimum critical region (MCR) for the RP28 gene in a 1.06 cM region between D2S2225 and D2S296. CONCLUSIONS : The present data confirmed linkage of arRP to the RP28 locus in a second Indian family. The RP28 locus was previously mapped to a 16 cM region between D2S1337 and D2S286 in a single Indian family. Haplotype analysis in this family has further narrowed the MCR for the RP28 locus to a 1.06 cM region between D2S2225 and D2S296. Of 15 genes reported in the MCR, 14 genes (KIAA0903, OTX1, MDH1, UGP2, VPS54, PELI1, HSPC159, FLJ20080, TRIP-Br2, SLC1A4, KIAA0582, RAB1A, ACTR2, and SPRED2) are either expressed in the eye or retina. Further study needs to be done to test which of these genes is mutated in patients with RP linked to the RP28 locus.