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.

Robust heuristics for scalable optimization of complex SQL queries

Modern database systems incorporate a query optimizer to identify the most efficient "query execution plan" for executing the declarative SQL queries submitted by users. A dynamic-programming-based approach is used to exhaustively enumerate the combinatorially large search space of plan alternatives and, using a cost model, to identify the optimal choice. While dynamic programming (DP) works very well for moderately complex queries with up to around a dozen base relations, it usually fails to scale beyond this stage due to its inherent exponential space and time complexity. Therefore, DP becomes practically infeasible for complex queries with a large number of base relations, such as those found in current decision-support and enterprise management applications. To address the above problem, a variety of approaches have been proposed in the literature. Some completely jettison the DP approach and resort to alternative techniques such as randomized algorithms, whereas others have retained DP by using heuristics to prune the search space to computationally manageable levels. In the latter class, a well-known strategy is "iterative dynamic programming" (IDP) wherein DP is employed bottom-up until it hits its feasibility limit, and then iteratively restarted with a significantly reduced subset of the execution plans currently under consideration. The experimental evaluation of IDP indicated that by appropriate choice of algorithmic parameters, it was possible to almost always obtain "good" (within a factor of twice of the optimal) plans, and in the few remaining cases, mostly "acceptable" (within an order of magnitude of the optimal) plans, and rarely, a "bad" plan. While IDP is certainly an innovative and powerful approach, we have found that there are a variety of common query frameworks wherein it can fail to consistently produce good plans, let alone the optimal choice. This is especially so when star or clique components are present, increasing the complexity of th- e join graphs. Worse, this shortcoming is exacerbated when the number of relations participating in the query is scaled upwards.

Triangular Ising antiferromagnet in a staggered field

We study the equilibrium properties of the nearest-neighbor Ising antiferromagnet on a triangular lattice in the presence of a staggered field conjugate to one of the degenerate ground states. Using a mapping of the ground states of the model without the staggered field to dimer coverings on the dual lattice, we classify the ground states into sectors specified by the number of "strings." We show that the effect of the staggered field is to generate long-range interactions between strings. In the limiting case of the antiferromagnetic coupling constant J becoming infinitely large, we prove the existence of a phase transition in this system and obtain a finite lower bound for the transition temperature. For finite J, we study the equilibrium properties of the system using Monte Carlo simulations with three different dynamics. We find that in all the three cases, equilibration times for low-field values increase rapidly with system size at low temperatures. Due to this difficulty in equilibrating sufficiently large systems at low temperatures, our finite-size scaling analysis of the numerical results does not permit a definite conclusion about the existence of st phase transition for finite values of J. A surprising feature in the system is the fact that unlike usual glassy systems; a zero-temperature quench almost always leads to the ground state, while a slow cooling does not.

Community-based Natural Resource Management: Issues and Cases from South Asia

Community-based natural resource management (CBNRM) is the joint management of natural resources by a community based on a community strategy, through a participatory mechanism involving all legitimate stakeholders. The approach is community-based in that the communities managing the resources have the legal rights, the local institutions and the economic incentives to take substantial responsibility for sustained use of these resources. This implies that the community plays an active role in the management of natural resources, not because it asserts sole ownership over them, but because it can claim participation in their management and benefits for practical and technical reasons1–4. This approach emerged as the dominant conservation concept in the late 1970s and early 1980s, of the disillusionment with the developmental state. Governments across South and South East Asia, Africa and Latin America have adopted and implemented CBNRM in various ways, viz. through sectoral programmes such as forestry, irrigation or wildlife management, multisectoral programmes such as watershed development and efforts towards political devolution. In India, the principle of decentralization through ‘gram swaraj’ was introduced by Mahatma Gandhi. The 73rd and 74th constitution amendments in 1992 gave impetus to the decentralized planning at panchayat levels through the creation of a statutory three-level local self-government structure5,6. The strength of this book is that it includes chapters by CBNRM advocates based on six seemingly innovative initiatives being implemented by nongovernmental organizations (NGOs) in ecologically vulnerable regions of South Asia: two in the Himalayas (watershed development programme in Lingmutechhu, Bhuthan and Thalisain tehsil, Paudi Grahwal District, Uttarakhand), three in semi-arid parts of western India (watershed development in Hivre Bazar, Maharashtra and Nathugadh village, Gujarat and water-harvesting structures in Gopalapura, Rajasthan) and one in the flood-plains of the Brahmaputra–Jamuna (Char land, Galibanda and Jamalpur districts, Bangladesh). Watersheds in semi-arid regions fall in the low-rainfall region (500–700 mm) and suffer the vagaries of drought 2–3 years in every five-year cycle. In all these locations, the major occupation is agriculture, most of which is rainfed or dry. The other two cases (in Uttarakhand) fall in the Himalayan region (temperate/sub-temperate climate), which has witnessed extensive deforestation in the last century and is now considered as one of the most vulnerable locations in South Asia. Terraced agriculture is being practised in these locations for a long time. The last case (Gono Chetona) falls in the Brahmaputra–Jamuna charlands which are the most ecologically vulnerable regions in the sub-continent with constantly changing landscape. Agriculture and livestock rearing are the main occupations, and there is substantial seasonal emigration for wage labour by the adult males. River erosion and floods force the people to adopt a semi-migratory lifestyle. The book attempts to analyse the potential as well as limitations of NGOdriven CBNRM endeavours across agroclimatic regions of South Asia with emphasis on four intrinsically linked normative concerns, namely sustainability, livelihood enhancement, equity and demographic decentralization in chapters 2–7. Comparative analysis of these case studies done in chapter 8, highlights the issues that require further research while portraying the strengths and limits of NGO-driven CBNRM. In Hivre Bazar, the post-watershed intervention scenario is such that farmers often grow three crops in a year – kharif bajra, rabi jowar and summer vegetable crops. Productivity has increased in the dry lands due to improvement in soil moisture levels. The revival of johads in Gopalpura has led to the proliferation of wheat and increased productivity. In Lingmuteychhu, productivity gains have also arisen, but more due to the introduction of both local and high-yielding, new varieties as opposed to increased water availability. In the case of Gono Chetona, improvements have come due to diversification of agriculture; for example, the promotion of vegetable gardens. CBNRM interventions in most cases have also led to new avenues of employment and income generation. The synthesis shows that CBNRM efforts have made significant contributions to livelihood enhancement and only limited gains in terms of collective action for sustainable and equitable access to benefits and continuing resource use, and in terms of democratic decentralization, contrary to the objectives of the programme. Livelihood benefits include improvements in availability of livelihood support resources (fuelwood, fodder, drinking water), increased productivity (including diversification of cropping pattern) in agriculture and allied activities, and new sources of livelihood. However, NGO-driven CBNRM has not met its goal of providing ‘alternative’ forms of ‘development’ due to impediments of state policy, short-sighted vision of implementers and confrontation with the socio-ecological reality of the region, which almost always are that of fragmented communities (or communities in flux) with unequal dependence and access to land and other natural resources along with great gender imbalances. Appalling, however, is the general absence of recognition of the importance of and the will to explore practical ways to bring about equitable resource transfer or benefit-sharing and the consequent innovations in this respect that are evident in the pioneering community initiatives such as pani panchayat, etc. Pertaining to the gains on the ecological sustainability front, Hivre Bazar and Thalisain initiatives through active participation of villagers have made significant regeneration of the water table within the village, and mechanisms such as ban on number of bore wells, the regulation of cropping pattern, restrictions on felling of trees and free grazing to ensure that in the future, the groundwater is neither over-exploited nor its recharge capability impaired. Nevertheless, the longterm sustainability of the interventions in the case of Ghoga and Gopalpura initiatives as the focus has been mostly on regeneration of resources, and less on regulating the use of regenerated resources. Further, in Lingmuteychhu and Gono Chetona, the interventions are mainly household-based and the focus has been less explicit on ecological components. The studies demonstrate the livelihood benefits to all of the interventions and significant variation in achievements with reference to sustainability, equity and democratic decentralization depending on the level and extent of community participation apart from the vision of implementers, strategy (or nature of intervention shaped by the question of community formation), the centrality of community formation and also the State policy. Case studies show that the influence of State policy is multi-faceted and often contradictory in nature. This necessitates NGOs to engage with the State in a much more purposeful way than in an ‘autonomous space’. Thus the role of NGOs in CBNRM is complementary, wherein they provide innovative experiments that the State can learn. This helps in achieving the goals of CBNRM through democratic decentralization. The book addresses the vital issues related to natural resource management and interests of the community. Key topics discussed throughout the book are still at the centre of the current debate. This compilation consists of well-written chapters based on rigorous synthesis of CBNRM case studies, which will serve as good references for students, researchers and practitioners in the years to come.

Structure and dynamics of protein excited states with millisecond lifetimes

An in-depth understanding of biological processes often requires detailed atomic resolution structures of the molecules involved. However in solution where most of these processes occur the conformation of biomolecules like RNA, DNA and proteins is not static but fluctuates. Routinely used structural techniques like X-ray crystallography, NMR spectroscopy and cryo-electron microscopy have almost always been used to determine the structure of the dominant conformation or obtain an average structure of the biomolecule in solution with very little detailed information regarding the dynamics of these molecules in solution. Over the last few years, NMR based methods have been developed to study the dynamics of these biomolecules in solution in a site-specific manner with the aim of generating structures of the different conformations that these molecules can adopt in solution. One powerful technique is the Carr-Purcell-Meiboom-Gill (CPMG) relaxation dispersion experiment, which can be used to detect and characterize protein excited states that are populated for as less as 0.5% of the time with ∼0.5–10 millisecond lifetimes. Due to recent advances in NMR pulse sequences and labeling methodology, it is now possible to determine the structures of these transiently populated excited states with millisecond lifetimes by obtaining accurate chemical shifts, residual dipolar couplings (RDCs) and residual chemical shift anisotropies (RCSAs) of these excited states. In these excited states the dynamics of some methyl containing residues can also be studied.

Scale-dependent relationships between tree species richness and ecosystem function in forests

1. The relationship between species richness and ecosystem function, as measured by productivity or biomass, is of long-standing theoretical and practical interest in ecology. This is especially true for forests, which represent a majority of global biomass, productivity and biodiversity. 2. Here, we conduct an analysis of relationships between tree species richness, biomass and productivity in 25 forest plots of area 8-50ha from across the world. The data were collected using standardized protocols, obviating the need to correct for methodological differences that plague many studies on this topic. 3. We found that at very small spatial grains (0.04ha) species richness was generally positively related to productivity and biomass within plots, with a doubling of species richness corresponding to an average 48% increase in productivity and 53% increase in biomass. At larger spatial grains (0.25ha, 1ha), results were mixed, with negative relationships becoming more common. The results were qualitatively similar but much weaker when we controlled for stem density: at the 0.04ha spatial grain, a doubling of species richness corresponded to a 5% increase in productivity and 7% increase in biomass. Productivity and biomass were themselves almost always positively related at all spatial grains. 4. Synthesis. This is the first cross-site study of the effect of tree species richness on forest biomass and productivity that systematically varies spatial grain within a controlled methodology. The scale-dependent results are consistent with theoretical models in which sampling effects and niche complementarity dominate at small scales, while environmental gradients drive patterns at large scales. Our study shows that the relationship of tree species richness with biomass and productivity changes qualitatively when moving from scales typical of forest surveys (0.04ha) to slightly larger scales (0.25 and 1ha). This needs to be recognized in forest conservation policy and management.

Environments of extended radio sources in the Australia Telescope Low-Brightness Survey

We present a study of the environments of extended radio sources in the Australia Telescope Low-Brightness Survey (ATLBS). The radio sources were selected from the ATLBS Extended Source Sample, which is a well defined sample containing the most extended of radio sources in the ATLBS sky survey regions. The environments were analysed using 4-m Cerro-Tololo Inter-American Observatory Blanco telescope observations carried out for ATLBS fields in the Sloan Digital Sky Survey r(') band. We have estimated the properties of the environments using smoothed density maps derived from galaxy catalogues constructed using these optical imaging data. The angular distribution of galaxy density relative to the axes of the radio sources has been quantified by defining anisotropy parameters that are estimated using a new method presented here. Examining the anisotropy parameters for a subsample of extended double radio sources that includes all sources with pronounced asymmetry in lobe extents, we find good evidence for environmental anisotropy being the dominant cause for lobe asymmetry in that higher galaxy density occurs almost always on the side of the shorter lobe, and this validates the usefulness of the method proposed and adopted here. The environmental anisotropy parameters have been used to examine and compare the environments of Fanaroff-Riley Class I (FRI) and Fanaroff-Riley Class II (FRII) radio sources in two redshift regimes (z < 0.5 and z > 0.5). Wide-angle tail sources and head-tail sources lie in the most overdense environments. The head-tail source environments (for the HT sources in our sample) display dipolar anisotropy in that higher galaxy density appears to lie in the direction of the tails. Excluding the head-tail and wide-angle tail sources, subsamples of FRI and FRII sources from the ATLBS appear to lie in similar moderately overdense environments, with no evidence for redshift evolution in the regimes studied herein.

Investigations of Ramachandran disallowed conformations in protein domain families

In peptide and protein structures, occurrence of (phi,psi.) angles in the disallowed region of the Ramachandran map almost always suggests local regions of error or poor accuracy. However, very rarely genuine disallowed conformations occur as noted in the current study in proteins of known structure available at ultra-high resolution (<= 1.2 (A) over circle). In the current work, extent of conservation of genuine disallowed conformations in homologous proteins of known structures has been analyzed. From a dataset of 124 protein domain families, with structure of at least one constituent member in each family available at a resolution of 1.2 (A) over circle or better, we have analyzed the conservation of 221 disallowed conformations. It is observed that the disallowed conformation is only moderately conservedin protein domain families. In the gross dataset no particular residue type adopting disallowed conformation elicit high conservation of residue type though there are alignment positions in the dataset with complete conservation of both the residue type and the disallowed conformation. Conserved disallowed conformation in protein domain families play biologically significant role in roughly 50% of the cases. The residues with the disallowed conformation or its flanking residues are often located within or around the functional site of the protein. (C) 2013 Elsevier B.V. All rights reserved.

Ramachandran analysis of conserved glycyl residues in homologous proteins of known structure

High conservation of glycyl residues in homologous proteins is fairly frequent. It is commonly understood that glycine tends to be highly conserved either because of its unique Ramachandran angles or to avoid steric clash that would arise with a larger side chain. Using a database of aligned 3D structures of homologous proteins we identified conserved Gly in 288 alignment positions from 85 families. Ninety-six of these alignment positions correspond to conserved Gly residue with (phi, ) values allowed for non-glycyl residues. Reasons for this observation were investigated by in-silico mutation of these glycyl residues to Ala. We found in 94% of the cases a short contact exists between the C atom of the introduced Ala with the atoms which are often distant in the primary structure. This suggests the lack of space even for a short side chain thereby explaining high conservation of glycyl residues even when they adopt (phi, ) values allowed for Ala. In 189 alignment positions, the conserved glycyl residues adopt (phi, ) values which are disallowed for Ala. In-silico mutation of these Gly residues to Ala almost always results in steric hindrance involving C atom of Ala as one would expect by comparing Ramachandran maps for Ala and Gly. Rare occurrence of the disallowed glycyl conformations even in ultrahigh resolution protein structures are accompanied by short contacts in the crystal structures and such disallowed conformations are not conserved in the homologues. These observations raise the doubt on the accuracy of such glycyl conformations in proteins.

A survey of indian logic from the point of view of computer science

Indian logic has a long history. It somewhat covers the domains of two of the six schools (darsanas) of Indian philosophy, namely, Nyaya and Vaisesika. The generally accepted definition of Indian logic over the ages is the science which ascertains valid knowledge either by means of six senses or by means of the five members of the syllogism. In other words, perception and inference constitute the subject matter of logic. The science of logic evolved in India through three ages: the ancient, the medieval and the modern, spanning almost thirty centuries. Advances in Computer Science, in particular, in Artificial Intelligence have got researchers in these areas interested in the basic problems of language, logic and cognition in the past three decades. In the 1980s, Artificial Intelligence has evolved into knowledge-based and intelligent system design, and the knowledge base and inference engine have become standard subsystems of an intelligent system. One of the important issues in the design of such systems is knowledge acquisition from humans who are experts in a branch of learning (such as medicine or law) and transferring that knowledge to a computing system. The second important issue in such systems is the validation of the knowledge base of the system i.e. ensuring that the knowledge is complete and consistent. It is in this context that comparative study of Indian logic with recent theories of logic, language and knowledge engineering will help the computer scientist understand the deeper implications of the terms and concepts he is currently using and attempting to develop.

Fuzzy logic intelligent system for gas turbine module and system fault isolation

A fuzzy logic intelligent system is developed for gas-turbine fault isolation. The gas path measurements used for fault isolation are exhaust gas temperature, low and high rotor speed, and fuel flow. These four measurements are also called the cockpit parameters and are typically found in almost all older and newer jet engines. The fuzzy logic system uses rules developed from a model of performance influence coefficients to isolate engine faults while accounting for uncertainty in gas path measurements. It automates the reasoning process of an experienced powerplant engineer. Tests with simulated data show that the fuzzy system isolates faults with an accuracy of 89% with only the four cockpit measurements. However, if additional pressure and temperature probes between the compressors and before the burner, which are often found in newer jet engines, are considered, the fault isolation accuracy rises to as high as 98%. In addition, the additional sensors are useful in keeping the fault isolation system robust as quality of the measured data deteriorates.

Fuzzy Logic-Based Approaches in Water Resource System Modelling

Recent research in modelling uncertainty in water resource systems has highlighted the use of fuzzy logic-based approaches. A number of research contributions exist in the literature that deal with uncertainty in water resource systems including fuzziness, subjectivity, imprecision and lack of adequate data. This chapter presents a broad overview of the fuzzy logic-based approaches adopted in addressing uncertainty in water resource systems modelling. Applications of fuzzy rule-based systems and fuzzy optimisation are then discussed. Perspectives on the scope for further research are presented.

A study of placement algorithms through trial interchange of logic modules

Based on trial interchanges, this paper develops three algorithms for the solution of the placement problem of logic modules in a circuit. A significant decrease in the computation time of such placement algorithms can be achieved by restricting the trial interchanges to only a subset of all the modules in a circuit. The three algorithms are simulated on a DEC 1090 system in Pascal and the performance of these algorithms in terms of total wirelength and computation time is compared with the results obtained by Steinberg, for the 34-module backboard wiring problem. Performance analysis of the first two algorithms reveals that algorithms based on pairwise trial interchanges (2 interchanges) achieve a desired placement faster than the algorithms based on trial N interchanges. The first two algorithms do not perform better than Steinberg's algorithm1, whereas the third algorithm based on trial pairwise interchange among unconnected pairs of modules (UPM) and connected pairs of modules (CPM) performs better than Steinberg's algorithm, both in terms of total wirelength (TWL) and computation time.

A Design for Testability of Undetectable Crosspoint Faults in Programmable Logic Arrays

In this paper, the validity of'single fault assumption in deriving diagnostic test sets is examined with respect to crosspoint faults in programmable logic arrays (PLA's). The control input procedure developed here can be used to convert PLA's having undetectable crosspoint faults to crosspoint-irredundant PLA's for testing purposes. All crosspoints will be testable in crosspoint-irredundant PLA's. The control inputs are used as extra variables during testing. They are maintained at logic I during normal operation. A useful heuristic for obtaining a near-minimal number of control inputs is suggested. Expressions for calculating bounds on the number of control inputs have also been obtained.

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.