An On-Line Algorithm for the Location of Cross Point Faults in Programmable Logic Arrays

An on-line algorithm is developed for the location of single cross point faults in a PLA (FPLA). The main feature of the valgorithm is the determination of a fault set corresponding to the response obtained for a failed test. For the apparently small number of faults in this set, all other tests are generated and a fault table is formed. Subsequently, an adaptive procedure is used to diagnose the fault. Functional equivalence test is carried out to determine the actual fault class if the adaptive testing results in a set of faults with identical tests. The large amount of computation time and storage required in the determination, a priori, of all the fault equivalence classes or in the construction of a fault dictionary are not needed here. A brief study of functional equivalence among the cross point faults is also made.

An (O)over-tilde(mn) Gomory-Hu Tree Construction Algorithm for Unweighted Graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V, E). The expected running time of our algorithm is (O) over tilde (mc) where vertical bar E vertical bar = m and c is the maximum u-v edge connectivity, where u, v is an element of V. When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n - 1; so the expected run-ning time of our algorithm for simple unweighted graphs is (O) over tilde (mn). All the algorithms currently known for constructing a Gomory-Hu tree [8, 9] use n - 1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest (O) over tilde (n(20/9)) max flow algorithm due to Karger and Levine[11] yields the current best running time of (O) over tilde (n(20/9)n) for Gomory-Hu tree construction on simple unweighted graphs with m edges and n vertices. Thus we present the first (O) over tilde (mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs. We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S subset of V can be reused for computing a minimum Steiner cut for certain Steiner sets S' subset of S.

Wall Shear Fluctuations in a Turbulent Boundary Layer

IN the last two decades, the instantaneous structure of a turbulent boundary layer has been examined by many in an effort to understand the dynamics of the flow. Distinct and well-defined flow patterns that seem to have great relevance to the turbulence production mechanism have been observed in the wall region.1'2 The flow near the wall is intermittent with periodic eruptions of the fluid, a phenomenon generally termed "bursting process." Earlier investigations in this field were limited to liquid flows at low speeds and the entire flowpattern was observed using flow visualization techniques.Study was later extended to boundary-layer flows in windtunnels at higher speeds and Reynolds numbers using hot-wiresignals for the analysis of the bursting phenomenon.

Performance Study of a Centralized Concurrency Control Algorithm for Distributed Database Systems using SIMULA

The stimulation technique has gained much importance in the performance studies of Concurrency Control (CC) algorithms for distributed database systems. However, details regarding the simulation methodology and implementation are seldom mentioned in the literature. One objective of this paper is to elaborate the simulation methodology using SIMULA. Detailed studies have been carried out on a centralised CC algorithm and its modified version. The results compare well with a previously reported study on these algorithms. Here, additional results concerning the update intensiveness of transactions and the degree of conflict are obtained. The degree of conflict is quantitatively measured and it is seen to be a useful performance index. Regression analysis has been carried out on the results, and an optimisation study using the regression model has been performed to minimise the response time. Such a study may prove useful for the design of distributed database systems.

In Situ Phase Separation Following Dehydration in Bimetallic Sulfates: A Variable-Temperature X-Ray Diffraction Study

Phase separation resulting in a single-crystal-single-crystal transition accompanied by a polycrystalline phase following the dehydration of hydrated bimetallic sulfates [Na2Mn1.167(SO4)(2)S0.33O1.167 center dot 2H(2)O and K4Cd3-(SO4)(5)center dot 3H(2)O] has been investigated by in situ variable-temperature single-crystal X-ray diffraction. With two examples, we illustrate the possibility of generating structural frameworks following dehydration in bimetallic sulfates, which refer to the possible precursor phases at that temperature leading to the mineral formation. The room-temperature structure of Na2Mn1.167(SO4)(2)S0.33O1.167 center dot 2H(2)O is trigonal, space group R (3) over bar. On heating the crystal in situ on the diffractometer, the diffraction images display spherical spots and concentric rings suggesting phase separation, with the spherical spots getting indexed in a monoclinic space group, C2/c. The structure determination based on this data suggests the formation of Na2Mn(SO4)(2). However, the diffraction images from concentric rings could not be indexed. In the second example, the room-temperature structure is determined to be K4Cd3(SO4)(5)center dot 3H(2)O, crystallizing in a monoclinic space group, P2(1)/n. On heating the crystal in situ, the diffraction images collected also have both spherical spots and diffuse rings. The spherical spots could be indexed to a cubic crystal system, space group P2(1)3, and the structure is K4Cd3(SO4)(3). The possible mechanism for the phase transition in the dehydration regime resulting in this remarkable single-crystal to single-crystal transition with the appearance of a surrogate polycrystalline phase is proposed.

Identification and analysis of extended strands and beta-sheets in globular proteins

A method to identify β-sheets in globular proteins from extended strands, using only α-carbon positions, has been developed. The strands that form β-sheets are picked up by means of simple distance criteria. The method has been tested by applying it to three proteins with accurately known secondary structures. It has also been applied to ten other proteins wherein only α-carbon coordinates are available, and the list of β-sheets obtained. The following points are worth noting: (i) The sheets identified by the algorithm are found to agree satisfactorily with the reported ones based on backbone hydrogen bonding, wherever this information is available. (ii) β-Strands that do not form parts of any sheet are a common feature of protein structures. (iii) Such isolated β-strands tend to be short. (iv) The conformation corresponding to the preferred right-handed twist of the sheet is overwhelmingly observed in both the sheet-forming and isolated β-strands.

An algorithm for optimum control of static VAR compensators to meet phase-wise unbalanced reactive power demands

The operation of thyristor-controlled static VAR compensators (SVCs) at various conduction angles can be used advantageously to meet the unablanced reactive power demands in a system. However, such operation introduces harmonic currents into the AC system. This paper presents an algorithm to evaluate an optimum combination of the phase-wise reactive power generations from SVC and balanced reactive power supply from the AC system, based on the defined performance indices, namely, the telephone influence factor (TIF), the total harmonic current factor (IT) and the distortion factor (D). Results of the studies conducted on a typical distribution system are presented and discussed.

Electroconductance in single-wall carbon nanotubes

A comparative study of the electric-field induced hopping transport probes the effective dimensionality (D) in bulk and ultrathin films of single-wall carbon nanotubes (SWNTs). The values of the scaling function exponents for the electroconductance are found to be consistent with that in three-dimensional and two-dimensional systems. The significant difference in threshold voltage in these two types of SWNTs is a consequence of the variation in the number of energetically favorable sites available for charge carriers to hop by using the energy from the field. Furthermore, a modification to the magnetotransport is observed under high electric-fields.

Approximation algorithm for maximum independent set in planar traingle-free graphs

The maximum independent set problem is NP-complete even when restricted to planar graphs, cubic planar graphs or triangle free graphs. The problem of finding an absolute approximation still remains NP-complete. Various polynomial time approximation algorithms, that guarantee a fixed worst case ratio between the independent set size obtained to the maximum independent set size, in planar graphs have been proposed. We present in this paper a simple and efficient, O(|V|) algorithm that guarantees a ratio 1/2, for planar triangle free graphs. The algorithm differs completely from other approaches, in that, it collects groups of independent vertices at a time. Certain bounds we obtain in this paper relate to some interesting questions in the theory of extremal graphs.

Trehalose toxicity in cuscuta-reflexa - cell-wall synthesis is inhibited upon trehalose feeding

a,a-Trehalose induced a rapid blackening of the terminal 2.5-centimete region of excised Cuscuta relexa Roxb. vine. The incorporation of radioactivite from [I'C]glucose into alkali-insoluble fraction of shoot tip was markedly inhibited by 12 hours of trehalose feeding to an excised vine. This inhibition was confied to the apical segment of the vine in which cell elongation occurred. The rate of blackening of shoot tip explants was hastened by the addition of gibberellic acid A3, which promoted elongationgrowth of isolated Cuscuta shoot tips. The symptom of trehalose toxicity was duplicated by 2-deoxygucose, which has been shown to ba potent inhibitor of ceD wall synthesis in yeast. The observations suggest that trehalose interferes with the synthesis of ceDl wail polysaccharides, the chief component of which was presumed to be cellulose.

A Branch and Bound Algorithm for a Transportation Type Problem with Piecewise Linear Convex Objective Function

A branch and bound type algorithm is presented in this paper to the problem of finding a transportation schedule which minimises the total transportation cost, where the transportation cost over each route is assumed to be a piecewice linear continuous convex function with increasing slopes. The algorithm is an extension of the work done by Balachandran and Perry, in which the transportation cost over each route is assumed to beapiecewise linear discontinuous function with decreasing slopes. A numerical example is solved illustrating the algorithm.

A note on mass transfer in turbulent wall jets

THE PROCESS of mass transfer from saturated porous surfaces virtual origin ; exposed to turbulent air streams finds many practical applitransverse coordinate; cations. In many cases, the air stream will be in the form of a height of nozzle above flat plate--radial wall jet; wall jet over the porous surface. The aerodynamics of both plane and radial wall jets have been investigated in detail and a vast amount of literature is available on the subject [l-3].

Optimal simultaneous maximum a posterioriestimation of states, noise statistics and parameters I. Algorithm

The simultaneous state and parameter estimation problem for a linear discrete-time system with unknown noise statistics is treated as a large-scale optimization problem. The a posterioriprobability density function is maximized directly with respect to the states and parameters subject to the constraint of the system dynamics. The resulting optimization problem is too large for any of the standard non-linear programming techniques and hence an hierarchical optimization approach is proposed. It turns out that the states can be computed at the first levelfor given noise and system parameters. These, in turn, are to be modified at the second level.The states are to be computed from a large system of linear equations and two solution methods are considered for solving these equations, limiting the horizon to a suitable length. The resulting algorithm is a filter-smoother, suitable for off-line as well as on-line state estimation for given noise and system parameters. The second level problem is split up into two, one for modifying the noise statistics and the other for modifying the system parameters. An adaptive relaxation technique is proposed for modifying the noise statistics and a modified Gauss-Newton technique is used to adjust the system parameters.

A parallel wilf algorithm for complex zeros of a polynomial

A global recursive bisection algorithm is described for computing the complex zeros of a polynomial. It has complexityO(n 3 p) wheren is the degree of the polynomial andp the bit precision requirement. Ifn processors are available, it can be realized in parallel with complexityO(n 2 p); also it can be implemented using exact arithmetic. A combined Wilf-Hansen algorithm is suggested for reduction in complexity.