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.

Analysing Message Sequence Graph Specifications

We give a detailed construction of a finite-state transition system for a com-connected Message Sequence Graph. Though this result is well-known in the literature and forms the basis for the solution to several analysis and verification problems concerning MSG specifications, the constructions given in the literature are either not amenable to implementation, or imprecise, or simply incorrect. In contrast we give a detailed construction along with a proof of its correctness. Our transition system is amenable to implementation, and can also be used for a bounded analysis of general (not necessarily com-connected) MSG specifications.

Development of a clean bioelectrochemical process for leaching of ocean manganese nodules

Through the application of negative reduction potential significant reduction of manganic and iron oxides in the ocean manganese nodules can be achieved, liberating the occluded copper, nickel and cobalt for easy dissolution in an acid medium. Electroleaching and electrobioleaching of ocean manganese nodules in the presence of Thiobacillus ferrooxidans and Thiobacillus thiooxidans at the above negative applied dc potentials resulted in significant dissolution of copper, nickel and cobalt in 1 M H2SO4. The role of galvanic interactions in the bioleaching of ocean manganese nodules in the presence of T thiooxidans is also discussed, (C) 2002 Published by Elsevier Science Ltd.

Acyclic Edge-Coloring of Planar Graphs

A proper edge-coloring with the property that every cycle contains edges of at least three distinct colors is called an acyclic edge-coloring. The acyclic chromatic index of a graph G, denoted. chi'(alpha)(G), is the minimum k such that G admits an acyclic edge-coloring with k colors. We conjecture that if G is planar and Delta(G) is large enough, then chi'(alpha) (G) = Delta (G). We settle this conjecture for planar graphs with girth at least 5. We also show that chi'(alpha) (G) <= Delta (G) + 12 for all planar G, which improves a previous result by Fiedorowicz, Haluszczak, and Narayan Inform. Process. Lett., 108 (2008), pp. 412-417].

Modelling, simulation, and graphical user interface for industrial gas carburising process

A mathematical model has been developed for the gas carburising (diffusion) process using finite volume method. The computer simulation has been carried out for an industrial gas carburising process. The model's predictions are in good agreement with industrial experimental data and with data collected from the literature. A study of various mass transfer and diffusion coefficients has been carried out in order to suggest which correlations should be used for the gas carburising process. The model has been interfaced in a Windows environment using a graphical user interface. In this way, the model is extremely user friendly. The sensitivity analysis of various parameters such as initial carbon concentration in the specimen, carbon potential of the atmosphere, temperature of the process, etc. has been carried out using the model.

Strategies for efficient start-up of continuous biooxidation process for refractory gold ores

Strategies for efficient start-up of a continuous process for biooxidation of refractory gold ore and concentrate obtained from Hutti, Gold Mines Limited (HGML), India are discussed in this work. The biooxidation of the concentrate at high pulp density (10%) with wild strain of Thiobacillus ferrooxidans isolated from HGML mines is characterized by significant lag phase (20 days) and incomplete oxidation (35%) even after prolonged operation (60 days). Two strategies, biooxidation with concentrate adapted cells and a step leaching strategy, in which the pulp density is progressively increased from 2% to 10% were considered and the latter resulted in efficient biooxidation of concentrate. Conversion of such a process from batch to continuous operation is shown to result in complete biooxidation of the concentrate and gold extraction efficiency in excess of 90%. (C) 2002 Elsevier Science Ltd. All rights reserved.

Study of formation of silicon carbide in the Acheson process

Formation of silicon carbide in the Acheson process was studied using a mass transfer model which has been developed in this study. The century old Acheson process is still used for the mass production of silicon carbide. A heat resistance furnace is used in the Acheson process which uses sand and petroleum coke as major raw materials.: It is a highly energy intensive process. No mass transfer model is available for this process. Therefore, a mass transfer model has been developed to study the mass transfer aspects of the process along with heat transfer. The reaction kinetics of silicon carbide formation has been taken from the literature. It has been shown that reaction kinetics has a reasonable influence on the process efficiency. The effect of various parameters on the process such as total gas pressure, presence of silicon carbide in the initial charge, etc. has been studied. A graphical user interface has also been developed for the Acheson process to make the computer code user friendly.

Three-dimensional computational modeling of momentum, heat, and mass transfer in a laser surface alloying process

A three- dimensional, transient model is developed for studying heat transfer, fluid flow, and mass transfer for the case of a single- pass laser surface alloying process. The coupled momentum, energy, and species conservation equations are solved using a finite volume procedure. Phase change processes are modeled using a fixed-grid enthalpy-porosity technique, which is capable of predicting the continuously evolving solid- liquid interface. The three- dimensional model is able to predict the species concentration distribution inside the molten pool during alloying, as well as in the entire cross section of the solidified alloy. The model is simulated for different values of various significant processing parameters such as laser power, scanning speed, and powder feedrate in order to assess their influences on geometry and dynamics of the pool, cooling rates, as well as species concentration distribution inside the substrate. Effects of incorporating property variations in the numerical model are also discussed.

Quasicrystalline Coatings Through Laser Processing: A Study on Process Optimisation and Microstructure Evolution

Composite coatings containing quasicrystalline (QC) phases in Al-Cu-Fe alloys were prepared by laser cladding using a mixture of the elemental powders. Two substrates, namely pure aluminum and an Al-Si alloy were used. The clad layers were remelted at different scanning velocities to alter the growth conditions of different phases. The process parameters were optimized to produce quasicrystalline phases. The evolution of the microstructure in the coating layer was characterized by detailed microstructural investigation. The results indicate presence of quasicrystals in the aluminum substrate. However, only approximant phase could be observed in the substrate of Al-Si alloys. It is shown that there is a significant transport of Si atoms from the substrate to the clad layer during the cladding and remelting process. The hardness profiles of coatings on aluminum substrate indicate a very high hardness. The coating on Al-Si alloy, on the other hand, is ductile and soft. The fracture toughness of the hard coating on aluminum was obtained by nano-indentation technique. The K1C value was found to be 1.33 MPa m1/2 which is typical of brittle materials.

Understanding the building-up process of three dimensional open-framework metal phosphates: Acid degradation of the 3D structures to lower dimensional structures

Acid degradation of 3D zinc phosphates primarily yields a one-dimensional ladder compound, an observation that is significant considering that the latter forms 3D structures on heating in water.

Performance Evaluation of Distance-Hop Proportionality on Geometric Graph Models of Dense Sensor Networks

Wireless sensor networks can often be viewed in terms of a uniform deployment of a large number of nodes on a region in Euclidean space, e.g., the unit square. After deployment, the nodes self-organise into a mesh topology. In a dense, homogeneous deployment, a frequently used approximation is to take the hop distance between nodes to be proportional to the Euclidean distance between them. In this paper, we analyse the performance of this approximation. We show that nodes with a certain hop distance from a fixed anchor node lie within a certain annulus with probability approach- ing unity as the number of nodes n → ∞. We take a uniform, i.i.d. deployment of n nodes on a unit square, and consider the geometric graph on these nodes with radius r(n) = c q ln n n . We show that, for a given hop distance h of a node from a fixed anchor on the unit square,the Euclidean distance lies within [(1−ǫ)(h−1)r(n), hr(n)],for ǫ > 0, with probability approaching unity as n → ∞.This result shows that it is more likely to expect a node, with hop distance h from the anchor, to lie within this an- nulus centred at the anchor location, and of width roughly r(n), rather than close to a circle whose radius is exactly proportional to h. We show that if the radius r of the ge- ometric graph is fixed, the convergence of the probability is exponentially fast. Similar results hold for a randomised lattice deployment. We provide simulation results that il- lustrate the theory, and serve to show how large n needs to be for the asymptotics to be useful.

A low power, process invariant keeper design for high speed dynamic logic circuits

A low power keeper circuit using the concept of rate sensing has been proposed. The proposed technique reduces the amount of short circuit power dissipation in the domino gate by 70% compared to the conventional keeper technique. Also the total power-delay product is 26% lower compared to the previously reported techniques. The process tracking capability of the design enables the domino gate to achieve uniform delay across different process corners. This reduces the amount of short circuit power dissipation that occurs in the cascaded domino gates by 90%. The use of the proposed technique in the read path of a register file reduces the energy requirement by 26% as compared to the other keeper techniques. The proposed technique has been prototyped in 130nm CMOS technology.