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.

A current error space vector based hysteresis controller with constant switching frequency and simple online boundary computation for VSI fed IM drive

This paper proposes a simple current error space vector based hysteresis controller for two-level inverter fed Induction Motor (IM) drives. This proposed hysteresis controller retains all advantages of conventional current error space vector based hysteresis controllers like fast dynamic response, simple to implement, adjacent voltage vector switching etc. The additional advantage of this proposed hysteresis controller is that it gives a phase voltage frequency spectrum exactly similar to that of a constant switching frequency space vector pulse width modulated (SVPWM) inverter. In this proposed hysteresis controller the boundary is computed online using estimated stator voltages along alpha and beta axes thus completely eliminating look up tables used for obtaining parabolic hysteresis boundary proposed in. The estimation of stator voltage is carried out using current errors along alpha and beta axes and steady state model of induction motor. The proposed scheme is simple and capable of taking inverter upto six step mode operation, if demanded by drive system. The proposed hysteresis controller based inverter fed drive scheme is simulated extensively using SIMULINK toolbox of MATLAB for steady state and transient performance. The experimental verification for steady state performance of the proposed scheme is carried out on a 3.7kW IM.

Polarization switching studies in ferroelectric glycine phosphite single crystals

Glycine Phosphite [NH3CH2COOH3PO3], abbreviated as GPI, undergoes a para-ferroelectric phase transition from the monoclinic symmetry P2(1)/a to P2(1) at 224.7 K. We report here a systematic study of the polarization switching process in this crystal. Growth of these crystals from aqueous solution has been undertaken employing both solvent evaporation and slow cooling methods. Hysteresis loop measurements along the polar b-axis yielded a spontaneous polarization value of 0.5 muC/cm(2) and a coercive field of 2.5 kV/cm. Conventional Merz technique was employed for polarization switching studies, wherein bipolar square pulses were applied to the sample to induce domain reversal. The transient switching pulse that flows through the sample on application of the field was recorded. The maximum switching time required for domain switching was measured both as a function of electric field and temperature. The experimentally observed switching curves were fitted with the model based on the Pulvari-Kuebler theory of nucleation and growth of domains. From the experimental data, the values of mobility and activation field were obtained. It was observed that switching process in this crystal is predominantly governed by the forward growth of domain walls in the high field region. However, switching process in GPI crystal was found to be slower than that found in other glycine based ferroelectric crystals.

Reversible and irreversible switching processes in pure and lanthanum modified lead zirconate thin films

The mechanism of field induced phase switching in antiferroelectric lead zirconate and La-modified lead zirconate thin films has been analysed in terms of reversible and irreversible switching process under weak fields as a function of donor concentration. Extension of Rayleigh law of ferromagnetic materials to the present antiferroelectric and modified antiferroelectric compositions have clearly showed that origin of small signal dielectric permittivity is due to reversible domain wall motion. Rayleigh's constant, a measure of irreversible switching process, exhibited a slight increase with lower La3+ concentrations and followed by a gradual fall for higher concentration. This clearly illustrates that donor addition to antiferroelectric thin films controls the domain switching even under weak fields. (C) 2002 Elsevier Science B.V. All rights reserved.

Electrical switching in chalcogenide glasses - Some newer insights

The recent studies on the switching. behavior of several chalcogenide semiconductors indicate that there exists a close relation between the electrical switching and structural effects in these materials; the two network topological Thresholds, namely the Rigidity Percolation and the Chemical Threshold are found to influence considerably the composition dependence of the switching voltages/fields of many memory and threshold switching glasses. Further, changes in the coordination of constituent atoms are found to effect a change in the switching behavior (memory to threshold), Also, an interesting relation has been established between the type of switching exhibited and the thermal diffusivity of the material.

Reactivity switching and selective activation of C-1 or C-3 in 2,3-unsaturated thioglycosides

Reactivity switching and selective activation of C-1 or C-3 in 2,3-unsaturated thioglycosides, namely, 2,3-dideoxy-1-thio-D-hex-2-enopyranosides are reported. The reactivity switching allowed activation of either C-1 or C-3, with the use of either N-iodosuccinimide (NIS)/triflic acid (TfOH) or TfOH alone. C-1 glycosylation with alcohol acceptors occurred in the presence of NIS/TfOH, without the acceptors reacting at C-3. On the other hand, reaction of 2,3-unsaturated thioglycosides with alcohols mediated by triflic acid led to transposition of C-1 ethylthio-moiety to C-3 intramolecularly, to form 3-ethylthio-glycals. Resulting glycals underwent glycosylation with alcohols to afford 3-ethylthio-2-deoxy glycosides. However, when thiol was used as an acceptor, only a stereoselective addition at C-3 resulted, so as to form C-1, C-3 dithio-substituted 2-deoxypyranosides. (C) 2011 Elsevier Ltd. All rights reserved.

Composition tunable memory and threshold switching in Al20As xTe80− x semiconducting glasses

I-V studies indicate a composition dependent switching behavior (Memory or Threshold) in bulk Al20AsxTe80−x glasses, which is determined by the coordination and composition of aluminum. Investigations on temperature and thickness dependence of switching and structural studies on switched samples suggest thermal and electronic mechanisms of switching for the memory and threshold samples, respectively. The present results also show that these samples have a wider composition range of threshold behavior with lower threshold voltages compared to other threshold samples.

Efficient statistical modeling for the compression of tree structured intermediate code

We propose a scheme for the compression of tree structured intermediate code consisting of a sequence of trees specified by a regular tree grammar. The scheme is based on arithmetic coding, and the model that works in conjunction with the coder is automatically generated from the syntactical specification of the tree language. Experiments on data sets consisting of intermediate code trees yield compression ratios ranging from 2.5 to 8, for file sizes ranging from 167 bytes to 1 megabyte.

Nonvolatile unipolar resistive switching in ultrathin films of graphene and carbon nanotubes

We report unipolar resistive switching in ultrathin films of chemically produced graphene (reduced graphene oxide) and multiwalled carbon nanotubes. The two-terminal devices with yield >99% are made at room temperature by forming continuous films of graphene of thickness similar to 20 nm on indium tin oxide coated glass electrode, followed by metal (Au or Al) deposition on the film. These memory devices are nonvolatile, rewritable with ON/OFF ratios up to similar to 10(5) and switching times up to 10 mu s. The devices made of MWNT films are rewritable with ON/OFF ratios up to similar to 400. The resistive switching mechanism is proposed to be nanogap formation and filamentary conduction paths. (C) 2011 Elsevier Ltd. All rights reserved.

Electrical switching studies on AS(40)Te(60-x)Se(x) and As35Te65-xSex glasses

The I-V characteristics of bulk As40Te60-xSex and As35Te65-xSex glasses have been studied with a current sweep of 0-18 mA-0, over a wide range of compositions (4 less than or equal to x less than or equal to 22). All the glasses studied showed a threshold electrical switching behaviour. The number of switching cycles withstood by the samples has been found to depend on the ON-state current. It is seen that the switching voltages increase with increase in selenium content. Further, the switching voltages are found to be almost independent of the thickness of the sample (d), in the range 0.18-0.3 mm. Also, the switching voltages and the number of switching cycles withstood by the samples are found to decrease with temperature.

A Low-Complexity, Full-Rate, Full-Diversity 2x2 STBC with Golden Code's Coding Gain

This paper presents a low-ML-decoding-complexity, full-rate, full-diversity space-time block code (STBC) for a 2 transmit antenna, 2 receive antenna multiple-input multipleoutput (MIMO) system, with coding gain equal to that of the best and well known Golden code for any QAM constellation.Recently, two codes have been proposed (by Paredes, Gershman and Alkhansari and by Sezginer and Sari), which enjoy a lower decoding complexity relative to the Golden code, but have lesser coding gain. The 2 × 2 STBC presented in this paper has lesser decoding complexity for non-square QAM constellations,compared with that of the Golden code, while having the same decoding complexity for square QAM constellations. Compared with the Paredes-Gershman-Alkhansari and Sezginer-Sari codes, the proposed code has the same decoding complexity for nonrectangular QAM constellations. Simulation results, which compare the codeword error rate (CER) performance, are presented.

Multi-hop Cooperative Wireless Networks: Diversity Multiplexing Tradeoff and Optimal Code Design

We consider single-source single-sink (ss-ss) multi-hop relay networks, with slow-fading links and single-antenna half-duplex relay nodes. While two-hop cooperative relay networks have been studied in great detail in terms of the diversity-multiplexing tradeoff (DMT), few results are available for more general networks. In this paper, we identify two families of networks that are multi-hop generalizations of the two-hop network: K-Parallel-Path (KPP)networks and layered networks.KPP networks, can be viewed as the union of K node-disjoint parallel relaying paths, each of length greater than one. KPP networks are then generalized to KPP(I) networks, which permit interference between paths and to KPP(D) networks, which possess a direct link from source to sink. We characterize the DMT of these families of networks completely for K > 3. Layered networks are networks comprising of layers of relays with edges existing only between adjacent layers, with more than one relay in each layer. We prove that a linear DMT between the maximum diversity dmax and the maximum multiplexing gain of 1 is achievable for single-antenna fully-connected layered networks. This is shown to be equal to the optimal DMT if the number of relaying layers is less than 4.For multiple-antenna KPP and layered networks, we provide an achievable DMT, which is significantly better than known lower bounds for half duplex networks.For arbitrary multi-terminal wireless networks with multiple source-sink pairs, the maximum achievable diversity is shown to be equal to the min-cut between the corresponding source and the sink, irrespective of whether the network has half-duplex or full-duplex relays. For arbitrary ss-ss single-antenna directed acyclic networks with full-duplex relays, we prove that a linear tradeoff between maximum diversity and maximum multiplexing gain is achievable.Along the way, we derive the optimal DMT of a generalized parallel channel and derive lower bounds for the DMT of triangular channel matrices, which are useful in DMT computation of various protocols. We also give alternative and often simpler proofs of several existing results and show that codes achieving full diversity on a MIMO Rayleigh fading channel achieve full diversity on arbitrary fading channels. All protocols in this paper are explicit and use only amplify-and-forward (AF) relaying. We also construct codes with short block-lengths based on cyclic division algebras that achieve the optimal DMT for all the proposed schemes.Two key implications of the results in the paper are that the half-duplex constraint does not entail any rate loss for a large class of cooperative networks and that simple AF protocols are often sufficient to attain the optimal DMT

An improved sapce phasor based current hysteresis controller with reduced switching frequency variations using variable parabolic bands

A current error space phasor based simple hysteresis controller is proposed in this paper to control the switching frequency variation in two-level pulsewidth-modulation (PWM) inverter-fed induction motor (IM) drives. A parabolic boundary for the current error space phasor is suggested for the first time to obtain the switching frequency spectrum for output voltage with hysteresis controller similar to the constant switching frequency voltage-controlled space vector PWM-based IM drive. A novel concept of online variation of this parabolic boundary, which depends on the operating speed of motor, is presented. A generalized technique that determines the set of unique parabolic boundaries for a two-level inverter feeding any given induction motor is described. The sector change logic is self-adaptive and is capable of taking the drive up to the six-step mode if needed. Steady-state and transient performance of proposed controller is experimentally verified on a 3.7-kW IM drive in the entire speed range. Close resemblance of the simulation and experimental results is shown.