Neural Structures Using the Eigenstates of a Quantum Harmonic Oscillator

The main result of the paper is the use of orthogonal Hermite polynomials as the basis functions of feedforward neural networks. The proposed neural networks have some interesting properties: (i) the basis functions are invariant under the Fourier transform, subject only to a change of scale, (ii) the basis functions are the eigenstates of the quantum harmonic oscillator, and stem from the solution of Schrödinger's diffusion equation. The proposed feed-forward neural networks demonstrate the particle-wave nature of information and can be used in nonparametric estimation. Possible applications of the proposed neural networks include function approximation, image processing and system modelling.     

Algebraic properties of cryptosystem PGM

In the late 1970s Magliveras invented a private-key cryptographic system calledPermutation Group Mappings (PGM). PGM is based on the prolific existence of certain kinds of factorization sets, calledlogarithmic signatures, for finite permutation groups. PGM is an endomorphic system with message space ℤ_|G| for a given finite permutation groupG. In this paper we prove several algebraic properties of PGM. We show that the set of PGM transformations ℐ _G is not closed under functional composition and hence not a group. This set is 2-transitive on ℤ_|G| if the underlying groupG is not hamiltonian and not abelian. Moreover, if the order ofG is not a power of 2, then the set of transformations contains an odd permutation. An important consequence of these results is that the group generated by the set of transformations is nearly always the symmetric group ℒ_|G|. Thus, allowing multiple encryption, any permutation of the message space is attainable. This property is one of the strongest security conditions that can be offered by a private-key encryption system. S. S. Magliveras was supported in part by NSF/NSA Grant Number MDA904-82-H0001, by U.S. West Communications, and by the Center for Communication and Information Science of the University of Nebraska.     

Modeling of in situ monitored laser reflectance during MOCVD growth of HgCdTe

An effective way to in situ monitor the metalorganic chemical vapor deposition (MOCVD) of HgCdTe/CdTe/ZnTe on GaAs or GaAs/Si substrates is presented. Specular He-Ne laser reflectance was used to in situ monitor the growth rates, layer thickness, and morphology for each layer in the grown multilayer structure. In situ monitoring has enabled precise measurements of ZnTe nucleation and CdTe buffer layer thicknesses. Monitoring the constancy of reflectance during the thicker CdTe buffer growth where absorption in the CdTe reduces reflectance to just the surface component has led to optimum buffer growth ensuring good quality of subsequently grown HgCdTe. During the interdiffused multilayer process (IMP) HgCdTe growth, because multiple interfaces are present within the absorption length, a periodic reflectance signal is maintained throughout this growth cycle. A theoretical model was developed to extract IMP layer thicknesses from in situ recorded experimental data. For structures that required the growth of a larger band gap HgCdTe cap layer on top of a smaller band gap active layer, in situ monitored reflectance data allowed determination of alloy composition in the cap layer as well. Continuous monitoring of IMP parameters established the stability of growth conditions, translating into depth uniformity of the grown material, and allowed diagnosis of growth rate instabilities in terms of changes in the HgTe and CdTe parts of the IMP cycle. A unique advantage of in situ laser monitoring is the opportunity to perform “interactive” crystal growth, a development that is a key to real time MOCVD HgCdTe feedback growth control.     

Avoiding linear dependencies in LFSR test pattern generators

Linear Feedback Shift Registers (LFSRs) constitute a very efficient mechanism for generating pseudoexhaustive or pseudo-random test sets for the built-in self-testing of digital circuits. However, a well-known problem with the use of LFSRs is the occurrence of linear dependencies in the generated patterns. In this paper, we show for the first time that the amount of linear dependencies can be controlled by selecting appropriate characteristic polynomials and reordering the LFSR cells. We identify two classes of such polynomials which, by appropriate LFSR cell ordering, guarantee that a large ratio of linear dependencies cannot occur. Experimental results show significant enhancements on the fault coverage for pseudo-random testing and support the theoretical relation between minimization of linear dependencies and effective fault coverage.This work was partially supported by NSF grant MIP-9409905, a 1993–94 ACM/IEEE Design Automation Scholarship and a grant from Nissan Corporation. A preliminary version of this work appeared in A Class of Good Characteristic Polynomials for LFSR Test Pattern Generators, in Proc. of IEEE International Conference on Computer Design, Oct. 1994, pp. 292–295, where it received the ICCD'94 Best Paper Award.     

Randomized priority algorithms

Borodin, Nielsen and Rackoff [13] introduced the class of priority algorithms as a framework for modeling deterministic greedy-like algorithms. In this paper we address the effect of randomization in greedy-like algorithms. More specifically, we consider approximation ratios within the context of randomized priority algorithms. As case studies, we prove inapproximation results for two well-studied optimization problems, namely facility location and makespan scheduling.     

Human-and-Humanoid Postures Under External Disturbances: Modeling,Simulation, and Robustness. Part 2: Simulation and Robustness

The sophisticated method for mathematical modeling of humanoid robots formulated in Part 1 of this paper is applied here to the dynamic task of keeping a posture under disturbance, which is equally important to humans and humanoid robots. The idea of this work is to develop and realize a simulator tool for dynamic analysis of human-or-humanoid behavior under disturbances. To show the potentials and verify this tool, we comparatively analyze the robustness of some postures to external disturbance. At this stage of research we do not conduct real experiments with humans/humanoids but try to verify our simulation tool by relying on available experience. Therefore, the postures for comparison are taken from everyday life and from sports: upright standing, squat posture, and three karate postures. As the external disturbance we choose an impulse and a permanent force, both with variable direction and magnitude.     

Efficient PAC Learning for Episodic Tasks with Acyclic State Spaces

This paper considers the problem of computing an optimal policy for a Markov decision process, under lack of complete a priori knowledge of (1) the branching probability distributions determining the evolution of the process state upon the execution of the different actions, and (2) the probability distributions characterizing the immediate rewards returned by the environment as a result of the execution of these actions at different states of the process. In addition, it is assumed that the underlying process evolves in a repetitive, episodic manner, with each episode starting from a well-defined initial state and evolving over an acyclic state space. A novel efficient algorithm for this problem is proposed, and its convergence properties and computational complexity are rigorously characterized in the formal framework of computational learning theory. Furthermore, in the process of deriving the aforementioned results, the presented work generalizes Bechhofer’s “indifference-zone” approach for the ranking & selection problem, that arises in statistical inference theory, so that it applies to populations with bounded general distributions.

On the Optimality of Randomized Deadlock Avoidance Policies

This paper revisits the problem of selecting an optimal deadlock resolution strategy, when the selection criterion is the maximization of the system throughput, and the system is Markovian in terms of its timing and routing characteristics. This problem was recently addressed in some of our previous work, that (i) provided an analytical formulation for it, (ii) introduced the notion of randomized deadlock avoidance as a generalization of the more traditional approaches of deadlock prevention/avoidance, and detection and recovery, and (iii) provided a methodology for selecting the optimal randomized deadlock avoidance policy for a given resource allocation system (RAS) configuration. An issue that remained open in the problem treatment of that past work, was whether the proposed policy randomization is essential, i.e., whether there exist any RAS configurations for which a randomized deadlock avoidance policy is superior to any other policy that does not employ randomization. The work presented in this paper establishes that for the basic problem formulation where the only concern is the (unconstrained) maximization of the system throughput—or the other typical performance objectives of minimizing the system work-in-process and mean sojourn time—randomization of the deadlock resolution strategy is not essential. However, it is also shown that, sometimes, it can offer an effective mechanism for accommodating additional operational constraints, like the requirement for production according to a specified product mix. Furthermore, the undertaken analysis provides an analytical characterization of the dependence of the aforementioned performance measures on the transition rates relating to the various events of the underlying state space, which can be useful for the broader problem of synthesizing efficient scheduling policies for the considered class of resource allocation systems.