(Semi)alternating stack automata

New results concerning the space complexity of languages accepted by stack automata, alternating stack automata, and alternating pushdown automata are derived. Some of the results generalize previously known results.Work supported by NSF Grant MCS79-09967.Work supported by NSF Grant MCS78-01736.     

A linear time randomizing algorithm for searching ranked functions

Consider a setF ofn functions defined on a common intervalU. A ranked function overF is defined from the functions ofF by using order information such as thek largest function, the sum ofk largest functions, etc. We give a linear time randomizing algorithmic paradigm for finding local roots, optima, intersection points, etc., of ranked functions. The algorithm is generalized to the Cost Effective Resource Allocation Problem and to various variants of the Parametric Knapsack Problem.     

A note on finite-valued and finitely ambiguous transducers

We look at some decision problems concerning nondeterministic finite transducers. The problems concern finite-valuedness, finite ambiguity, equivalence, etc. For a fixedk, we give a polynomial time algorithm for deciding whether or not a transducer isk-valued. The result holds when “valued” is replaced by “ambiguous”. In fact, the following problems are decidable: 1) Given a transducer, is itk-ambiguous for somek? 2) Given two finitely ambiguous transducers, are they equivalent? For unambiguous transducers, equivalence is decidable in polynomial time.     

Detection of gaseous plumes in IR hyperspectral images using hierarchical clustering

The emergence of IR hyperspectral sensors in recent years enables their use in remote environmental monitoring of gaseous plumes. IR hyperspectral imaging combines the unique advantages of traditional remote sensing methods such as multispectral imagery and nonimaging Fourier transform infrared spectroscopy, while eliminating their drawbacks. The most significant improvement introduced by hyperspectral technology is the capability of standoff detection and discrimination of effluent gaseous plumes without need for a clear reference background or any other temporal information. We introduce a novel approach for detection and discrimination of gaseous plumes in IR hyperspectral imagery using a divisive hierarchical clustering algorithm. The utility of the suggested detection algorithm is demonstrated on IR hyperspectral images of the release of two atmospheric tracers. The application of the proposed detection method on the experimental data has yielded a correct identification of all the releases without any false alarms. These encouraging results show that the presented approach can be used as a basis for a complete identification algorithm for gaseous pollutants in IR hyperspectral imagery without the need for a clear background.     

Effects of Magnetic Field on Conductance and Electroluminescence in Organic Devices

In this contribution we review recent advances of the organic magnetic field effects, namely magneto-conductance and magneto-electroluminescence, in both experiment and theory. We describe a number of processes, including the polaron-pair and triplet-triplet pair mechanisms that are responsible for the magnetic field effects in organic semiconductor systems. For the polaron pair mechanism, we review in detail the effect of the hyperfine interaction, both isotropic and anisotropic; different g-factors of the two polarons composing the pair; and the spin orbit interaction. The effect of the triplet-triplet annihilation process is also analyzed. Experimental examples for each case treated theoretically are given.     

Recombination kinetics of polarons in films of alkylator-sensing co-polymers

We report on the effect of an alkylating agent sensing of a nucleophilic unit, Pyridine-Thiophene (PyTh), on the polaron recombination in a co-polymer [Poly(3-hexylthiophene)]_n(PyTh)_m (m≈0.025n$m\approx 0.025n$). We show that by exposing the co-polymer to an alkylating agent, such as methyl iodide, the recombination rate increases substantially, possibly due to the introduction of additional recombination pathways created by the charge transfer between the electron deficient alkylated pyridinium sites and the electron rich thiophene polymer backbone.     

Performance of ad hoc networks with two-hop relay routing and limited packet lifetime (extended version)

We consider a mobile ad hoc network consisting of three types of nodes (source, destination and relay nodes) and using the two-hop relay routing. This type of routing takes advantage of the mobility and the storage capacity of the nodes, called the relay nodes, in order to route packets between a source and a destination. Packets at relay nodes are assumed to have a limited lifetime in the network. Nodes are moving inside a bounded region according to some random mobility model. Closed-form expressions and asymptotic results when the number of nodes is large are provided for the packet delivery delay and for the energy needed to transmit a packet from the source to its destination. We also introduce and evaluate a variant of the two-hop relay protocol that limits the number of generated copies in the network. Our model is validated through simulations for two mobility models (random waypoint and random direction mobility models), and the performance of the two-hop routing and of the epidemic routing protocols are compared.