The complexity of certain incremental code generation problems

This paper looks at the complexity of four different incremental problems. The following are the problems considered: (1) Interval partitioning of a flow graph (2) Breadth first search (BFS) of a directed graph (3) Lexicographic depth first search (DFS) of a directed graph (4) Constructing the postorder listing of the nodes of a binary tree. The last problem arises out of the need for incrementally computing the Sethi-Ullman (SU) ordering [1] of the subtrees of a tree after it has undergone changes of a given type. These problems are among those that claimed our attention in the process of our designing algorithmic techniques for incremental code generation. BFS and DFS have certainly numerous other applications, but as far as our work is concerned, incremental code generation is the common thread linking these problems. The study of the complexity of these problems is done from two different perspectives. In [2] is given the theory of incremental relative lower bounds (IRLB). We use this theory to derive the IRLBs of the first three problems. Then we use the notion of a bounded incremental algorithm [4] to prove the unboundedness of the fourth problem with respect to the locally persistent model of computation. Possibly, the lower bound result for lexicographic DFS is the most interesting. In [5] the author considers lexicographic DFS to be a problem for which the incremental version may require the recomputation of the entire solution from scratch. In that sense, our IRLB result provides further evidence for this possibility with the proviso that the incremental DFS algorithms considered be ones that do not require too much of preprocessing.

Pattern-growth based frequent serial episode discovery

Frequent episode discovery is a popular framework for pattern discovery from sequential data. It has found many applications in domains like alarm management in telecommunication networks, fault analysis in the manufacturing plants, predicting user behavior in web click streams and so on. In this paper, we address the discovery of serial episodes. In the episodes context, there have been multiple ways to quantify the frequency of an episode. Most of the current algorithms for episode discovery under various frequencies are apriori-based level-wise methods. These methods essentially perform a breadth-first search of the pattern space. However currently there are no depth-first based methods of pattern discovery in the frequent episode framework under many of the frequency definitions. In this paper, we try to bridge this gap. We provide new depth-first based algorithms for serial episode discovery under non-overlapped and total frequencies. Under non-overlapped frequency, we present algorithms that can take care of span constraint and gap constraint on episode occurrences. Under total frequency we present an algorithm that can handle span constraint. We provide proofs of correctness for the proposed algorithms. We demonstrate the effectiveness of the proposed algorithms by extensive simulations. We also give detailed run-time comparisons with the existing apriori-based methods and illustrate scenarios under which the proposed pattern-growth algorithms perform better than their apriori counterparts. (C) 2013 Elsevier B.V. All rights reserved.

Construction of Block Orthogonal STBCs and Reducing Their Sphere Decoding Complexity

Construction of high rate Space Time Block Codes (STBCs) with low decoding complexity has been studied widely using techniques such as sphere decoding and non Maximum-Likelihood (ML) decoders such as the QR decomposition decoder with M paths (QRDM decoder). Recently Ren et al., presented a new class of STBCs known as the block orthogonal STBCs (BOSTBCs), which could be exploited by the QRDM decoders to achieve significant decoding complexity reduction without performance loss. The block orthogonal property of the codes constructed was however only shown via simulations. In this paper, we give analytical proofs for the block orthogonal structure of various existing codes in literature including the codes constructed in the paper by Ren et al. We show that codes formed as the sum of Clifford Unitary Weight Designs (CUWDs) or Coordinate Interleaved Orthogonal Designs (CIODs) exhibit block orthogonal structure. We also provide new construction of block orthogonal codes from Cyclic Division Algebras (CDAs) and Crossed-Product Algebras (CPAs). In addition, we show how the block orthogonal property of the STBCs can be exploited to reduce the decoding complexity of a sphere decoder using a depth first search approach. Simulation results of the decoding complexity show a 30% reduction in the number of floating point operations (FLOPS) of BOSTBCs as compared to STBCs without the block orthogonal structure.

Discriminating between natural and anthropogenic aerosol contributions to optical depth over Afro-Asian region

To accurately assess the impact of anthropogenic aerosols on climate, spatial and temporal distribution of its radiative properties is essential. The first step towards separating the radiative impact of natural aerosol from its anthropogenic counterparts is to gather information on natural aerosols. In this paper, we have used data from multiple satellites to derive the anthropogenic aerosol fraction (AAF) over the Afro-Asian region. The AAF was largest during the pre-monsoon season (May-June) and lowest during winter. We have shown that over desert locations the AAF was unexpectedly large (>0.4) and the regionally (and annually) averaged anthropogenic fraction over the Afro-Asian region was 0.54 +/- 0.12. Copyright (C) 2010 Royal Meteorological Society

Ricin-membrane interaction: membrane penetration depth by fluorescence quenching and resonance energy transfer

The entry of the plant toxin ricin and its A- and B-subunits in model membranes in the presence as well as absence of monosialoganglioside (GM(1)) has been studied. Dioleoylphosphatidylcholine and 5-, 10-, and 12-doxyl- or 9,10-dibromophosphatidylcholines serve as quenchers of intrinsic tryptophan fluorescence of the proteins. The parallax method of Chattopadhyay and London [(1987) Biochemistry 26, 39-45] has been employed to measure the average membrane penetration depth of tryptophans of ricin and its B-chain and the actual depth of the sole Trp 211 in the A-chain. The results indicate that both of the chains as well as intact ricin penetrate the membrane deeply and the C-terminal end of the A-chain is well inside the bilayer, especially at pH 4.5. An extrinsic probe N-(iodoacetyl)-N'-(5-sulfo-1-naphthyl) ethylenediamine (I-AEDANS) has been attached to Cys 259 of the A-chain, and the kinetics of penetration has been followed by monitoring the increase in AEDANS fluorescence at 480 nm. The insertion follows first-order kinetics, and the rate constant is higher at a lower pH. The energy transfer distance analysis between Trp 211 and AEDANS points out that the conformation of the A-chain changes as it inserts into the membrane. CD studies indicate that the helicity of the proteins increases after penetration, which implies that some of the unordered structure in the native protein is converted to the ordered form during this process. Hydrophobic forces seem to be responsible for stabilizing a particular protein conformation inside the membrane.

Trends in aerosol optical depth over Indian region: Potential causes and impact indicators

The first regional synthesis of long-term (back to similar to 25 years at some stations) primary data (from direct measurement) on aerosol optical depth from the ARFINET (network of aerosol observatories established under the Aerosol Radiative Forcing over India (ARFI) project of Indian Space Research Organization over Indian subcontinent) have revealed a statistically significant increasing trend with a significant seasonal variability. Examining the current values of turbidity coefficients with those reported similar to 50 years ago reveals the phenomenal nature of the increase in aerosol loading. Seasonally, the rate of increase is consistently high during the dry months (December to March) over the entire region whereas the trends are rather inconsistent and weak during the premonsoon (April to May) and summer monsoon period (June to September). The trends in the spectral variation of aerosol optical depth (AOD) reveal the significance of anthropogenic activities on the increasing trend in AOD. Examining these with climate variables such as seasonal and regional rainfall, it is seen that the dry season depicts a decreasing trend in the total number of rainy days over the Indian region. The insignificant trend in AOD observed over the Indo-Gangetic Plain, a regional hot spot of aerosols, during the premonsoon and summer monsoon season is mainly attributed to the competing effects of dust transport and wet removal of aerosols by the monsoon rain. Contributions of different aerosol chemical species to the total dust, simulated using Goddard Chemistry Aerosol Radiation and Transport model over the ARFINET stations, showed an increasing trend for all the anthropogenic components and a decreasing trend for dust, consistent with the inference deduced from trend in Angstrom exponent.

High Quality Photometric Reconstruction using a Depth Camera

In this paper we present a depth-guided photometric 3D reconstruction method that works solely with a depth camera like the Kinect. Existing methods that fuse depth with normal estimates use an external RGB camera to obtain photometric information and treat the depth camera as a black box that provides a low quality depth estimate. Our contribution to such methods are two fold. Firstly, instead of using an extra RGB camera, we use the infra-red (IR) camera of the depth camera system itself to directly obtain high resolution photometric information. We believe that ours is the first method to use an IR depth camera system in this manner. Secondly, photometric methods applied to complex objects result in numerous holes in the reconstructed surface due to shadows and self-occlusions. To mitigate this problem, we develop a simple and effective multiview reconstruction approach that fuses depth and normal information from multiple viewpoints to build a complete, consistent and accurate 3D surface representation. We demonstrate the efficacy of our method to generate high quality 3D surface reconstructions for some complex 3D figurines.

Enantiospecific first total synthesis of (-)-4-thiocyanatoneopupukeanane

The first total synthesis of (-)-4-thiocyanatoneopupukeanane starting from (R)-carvone has been achieved, establishing the relative as well as absolute structure of the natural product.

Regolith mass balance inferred from combined mineralogical, geochemical and geophysical studies: Mule Hole gneissic watershed, South India

The aim of this study is to propose a method to assess the long-term chemical weathering mass balance for a regolith developed on a heterogeneous silicate substratum at the small experimental watershed scale by adopting a combined approach of geophysics, geochemistry and mineralogy. We initiated in 2003 a study of the steep climatic gradient and associated geomorphologic features of the edge of the rifted continental passive margin of the Karnataka Plateau, Peninsular India. In the transition sub-humid zone of this climatic gradient we have studied the pristine forested small watershed of Mule Hole (4.3 km(2)) mainly developed on gneissic substratum. Mineralogical, geochemical and geophysical investigations were carried out (i) in characteristic red soil profiles and (ii) in boreholes up to 60 m deep in order to take into account the effect of the weathering mantle roots. In addition, 12 Electrical Resistivity Tomography profiles (ERT), with an investigation depth of 30 m, were generated at the watershed scale to spatially characterize the information gathered in boreholes and soil profiles. The location of the ERT profiles is based on a previous electromagnetic survey, with an investigation depth of about 6 m. The soil cover thickness was inferred from the electromagnetic survey combined with a geological/pedological survey. Taking into account the parent rock heterogeneity, the degree of weathering of each of the regolith samples has been defined using both the mineralogical composition and the geochemical indices (Loss on Ignition, Weathering Index of Parker, Chemical Index of Alteration). Comparing these indices with electrical resistivity logs, it has been found that a value of 400 Ohm m delineates clearly the parent rocks and the weathered materials, Then the 12 inverted ERT profiles were constrained with this value after verifying the uncertainty due to the inversion procedure. Synthetic models based on the field data were used for this purpose. The estimated average regolith thickness at the watershed scale is 17.2 m, including 15.2 m of saprolite and 2 m of soil cover. Finally, using these estimations of the thicknesses, the long-term mass balance is calculated for the average gneiss-derived saprolite and red soil. In the saprolite, the open-system mass-transport function T indicates that all the major elements except Ca are depleted. The chlorite and biotite crystals, the chief sources for Mg (95%), Fe (84%), Mn (86%) and K (57%, biotite only), are the first to undergo weathering and the oligoclase crystals are relatively intact within the saprolite with a loss of only 18%. The Ca accumulation can be attributed to the precipitation of CaCO3 from the percolating solution due to the current and/or the paleoclimatic conditions. Overall, the most important losses occur for Si, Mg and Na with -286 x 10(6) mol/ha (62% of the total mass loss), -67 x 10(6) mol/ha (15% of the total mass loss) and -39 x 10(6) mol/ha (9% of the total mass loss), respectively. Al, Fe and K account for 7%, 4% and 3% of the total mass loss, respectively. In the red soil profiles, the open-system mass-transport functions point out that all major elements except Mn are depleted. Most of the oligoclase crystals have broken down with a loss of 90%. The most important losses occur for Si, Na and Mg with -55 x 10(6) mol/ha (47% of the total mass loss), -22 x 10(6) mol/ha (19% of the total mass loss) and -16 x 10(6) mol/ha (14% of the total mass loss), respectively. Ca, Al, K and Fe account for 8%, 6%, 4% and 2% of the total mass loss, respectively. Overall these findings confirm the immaturity of the saprolite at the watershed scale. The soil profiles are more evolved than saprolite but still contain primary minerals that can further undergo weathering and hence consume atmospheric CO2.

First donor-acceptor interaction promoted gelation of organic fluids

In recent years there has been considerable interest in developing new types of gelators of organic solvents.1 Despite the recent advances, a priori design of a gelator for gelling a given solvent has remained a challenging task. Various noncovalent interactions like hydrogen-bonding,2 metal coordination3 etc. have been used as the driving force for the gelation process. A special class of cholesterol-based gelators were reported by Weiss,4 and by Shinkai.5 Gels derived from these molecules have been used for chiral recognition/sensing,6 for studying photo- and metal-responsive functions,7 and as templates to make hollow fiber silica.8 Other types of organogels have been used for designing polymerized 9 and reverse aerogels,10 and in molecular imprinting.11 Hanabusa’s group has recently reported organogels with a bile acid derivative.12 This has prompted us to disclose our results on a novel electron donor–acceptor (EDA) interaction mediated two-component13 gelator system based on the bile acid14 backbone.

First principles study of magnetism in divalent Eu perovskites

A comparative first principles study has been carried out for EuLiH3 (ELH) and EuTiO3 (ETO) using the generalized gradient approximation +U approach. While ELH exhibits ferromagnetic ground state for all volumes, the magnetic ground state of ETO has the tendency to switch from G-type antiferromagnetic to a ferromagnetic state with change in volume. The marked difference in magnetic behavior and magnitude of the nearest neighbors exchange interaction of both the compounds are shown to be related to the difference in their respective electronic structure near the Fermi level. The Ti 3d states are shown to play predominant role in weakening the strength of the exchange interaction in ETO.

The first observation of a Na2TiS2 related structure in a 2-D anionic manganese trimesate intercalated by cationic imidazole

A hydrothermal reaction of Mn(OAc)2·4H2O, trimesic acid, imidazole, KOH and water at 75 °C for 24 h gave rise to a 2-D compound, [HImd][Mn(BTC)(H2O)] (Imd = imidazole; BTC = trimesate), with protonated imidazole molecules occupying the inter-lamellar space, and the structure resembles the classic inorganic compound, the sodium intercalated TiS2 (Na2TiS2).

Spatial Variability of the Depth of Weathered and Engineering Bedrock using Multichannel Analysis of Surface Wave Method

In this paper an attempt has been made to evaluate the spatial variability of the depth of weathered and engineering bedrock in Bangalore, south India using Multichannel Analysis of Surface Wave (MASW) survey. One-dimensional MASW survey has been carried out at 58 locations and shear-wave velocities are measured. Using velocity profiles, the depth of weathered rock and engineering rock surface levels has been determined. Based on the literature, shear-wave velocity of 330 ± 30 m/s for weathered rock or soft rock and 760 ± 60 m/s for engineering rock or hard rock has been considered. Depths corresponding to these velocity ranges are evaluated with respect to ground contour levels and top surface levels have been mapped with an interpolation technique using natural neighborhood. The depth of weathered rock varies from 1 m to about 21 m. In 58 testing locations, only 42 locations reached the depths which have a shear-wave velocity of more than 760 ± 60 m/s. The depth of engineering rock is evaluated from these data and it varies from 1 m to about 50 m. Further, these rock depths have been compared with a subsurface profile obtained from a two-dimensional (2-D) MASW survey at 20 locations and a few selected available bore logs from the deep geotechnical boreholes.

Quantum first-passage problem

Formulation of quantum first passage problem is attempted in terms of a restricted Feynman path integral that simulates an absorbing barrier as in the corresponding classical case. The positivity of the resulting probability density, however, remains to be demonstrated.