Computer Sciences Commons^™

Lower Bounds On The Area Of Finite-State Machines, M. J. Foster, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

There are certain straightforward algorithms for laying out finite-state machines. This paper shows that these algorithm are optimal in the worst case for machines with fixed alphabets. That is, for any s and k, there is a deterministic finite-state machine with s states and k symbols such that any layout algorithm requires Ω(ks log s) area to lay out its realization. Similarly, any layout algorithm requires Ω(ks^2) area in the worst case for nondeterministic finite-state machines with s states and k symbols.

Euclidean Traveling Salesman Heuristics, Ron Greenberg, Cindy Phillips, Joel Wein

Computer Science: Faculty Publications and Other Works

No abstract provided.

Wide-Sense Nonblocking Networks, Paul Feldman, Joel Friedman, Nicholas Pippenger

All HMC Faculty Publications and Research

A new method for constructing wide-sense nonblocking networks is presented. Application of this method yields (among other things) wide-sense nonblocking generalized connectors with n inputs and outputs and size O( n log n ), and with depth k and size O( n^{1 + 1/k} ( log n )^{1 - 1/k} ).

Software Tools For Performance Evaluation Of Concurrent Processing, Rodrogo A. Obando

Electrical & Computer Engineering Theses & Dissertations

The development and use of software tools for performance evaluation of concurrent processing is presented in this thesis. The particular concurrent processing architecture proposed by Stoughton and Mielke is investigated. The modelling of this architecture is based on Petri net theory and it can be studied making use of circuit theory. Computation of lower bounds for Time Between Outputs (TBO) and Time Between Input and Output (TBIO) can be accomplished by using principles of circuit theory, among others. This new modelling needs to be deeply evaluated and studied. This evaluation and study is accomplished with the tools developed and presented …

Wind Streamline Ambiguity Removal Of Microwave Scatterometer Data, Hans W. Zaepfel

Electrical & Computer Engineering Theses & Dissertations

There is a class of satellite microwave scatterometers that return oceanographic information which includes wind vectors with directional ambiguity. The first part of the ambiguity removal process is to reduce the data to a directional ambiguity of 180°. This thesis shows that wind direction change contains the information required for streamline ambiguity removal and that syntactic pattern recognition techniques can be used to locate the areas of wind direction change. Spreading the information along the areas of wind direction change results in the removal of the streamline ambiguity. The algorithm is implemented and the results are presented showing that it …

High Performance Switching Circuits For Vlsi, Ali Reza Feizi

Electrical & Computer Engineering Theses & Dissertations

Interconnection topology and device performance are of major concern in the design of LSI/VLSI systems, Pass networks are very suitable in this regard because of low power consumption, high density, and simple interconnection topology. A special type of pass networks called Binary Tree Structured (BTS) pass networks uses almost minimum number of transistors for the design of switching circuits. An algorithmic procedure is developed here for BTS pass networks which is very efficient in terms of both execution time and memory space. Based on these networks, the necessary and sufficient conditions are derived for the design of multiple-output pass networks. …

Randomized Routing On Fat-Trees, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(lambda+lgnlglgn) with probability 1-O(1/ …

Analog Computer Simulation With Automatic Scaling By Digital Computer, Mark Anthony Motter

Electrical & Computer Engineering Theses & Dissertations

A computer-aided design approach for the simplification of analog computer simulation is presented. The simulation configuration consists of an EAI 2000 analog computer with serial communications link to a PDP — 11/24 digital computer. Under control of the PDP-11, the analog simulations are realized with appropriate time and magnitude scaling which adjusts the range of the simulation coefficients and prevents overloads of the analog components. The analog computer hardware configuration accommodates both stable plants up to eighth order and closed-loop systems up to tenth order. Cascade compensation is provided for the closed-loop systems.

The plant may be described by either …

Design Of Infrasound-Detection System Via Adaptive Lmstde Algorithm, Camille S. Khalaf

Electrical & Computer Engineering Theses & Dissertations

A proposed solution to an aviation safety problem is based on passive detection of turbulent weather phenomena through their infrasonic emission. This thesis describes a system design that is adequate for detection and bearing evaluation of infrasounds. An array of four sensors, with the appropriate hardware, is used for the detection part. Bearing evaluation is based on estimates of time delays between sensor outputs. The generalized cross correlation (GCC), as the conventional time-delay estimation (TOE) method, is first reviewed. An adaptive TUt approach, using the least mean square (LMS) algorithm, is then discussed. A comparison between the two techniques is …

Suboptimal Algorithms For Improvement Of Pipeline Through Insertion Of Delays, Sukhamoy Som

Electrical & Computer Engineering Theses & Dissertations

Pipelining is now widely used in the design of high speed processors in order to overcome the intrinsic speed limitations imposed by the technology. For a good performance and avoidance of internal conflicts, the concurrent operations within different subunits of a pipeline architecture should be properly scheduled This scheduling problem is known to be intrinsically difficult" and a member of the "NP complete class of problems. The aim of this thesis is to develop heuristic suboptimal algorithms whose execution time is a polynomial function of the number of items to be scheduled. Insertion of delay is used as a basic …

Block Encoding Of Speech Spectral Principal Components, James R. Holland Jr.

Electrical & Computer Engineering Theses & Dissertations

A Karhunen-Loeve series expansion was used to block encode speech spectral principal components as a function of time. Each of ten principal components was first obtained as a linear combination of 2© speech spectral band energies. Using a fixed block length of 10 frames (0.128 s), the K-L basis vectors were computed separately for various speakers for each principal component. In all cases the resulting basis vectors were essentially a set of discrete cosine basis vectors. Synthesis of speech from the block encoded parameters showed that very little information is lost with up to 70% data reduction. The block encoding …

On Monotone Formulae With Restricted Depth, Maria M. Klawe, Wolfgang J. Paul, Nicholas J. Pippenger, Mihalis Yannakakis

All HMC Faculty Publications and Research

We prove a hierarchy theorem for the representation of monotone Boolean functions by monotone Boolean functions by monotone formulae with restricted depth. Specifically, we show that there are functions with Π_k-formulae of size n for which every Σ_k-formula has size exp Ω(n^1/(k-1)). A similar lower bound applies to concrete functions such as transitive closure and clique. We also show that any function with a formula of size n (and any depth) has a Σ_k-formula of size exp O(n^1/(k-1)). Thus our hierarchy theorem is the best possible.

Probabilistic Simulations, Nicholas J. Pippenger

All HMC Faculty Publications and Research

The results of this paper concern the question of how fast machines with one type of storage media can simulate machines with a different type of storage media. Most work on this question has focused on the question of how fast one deterministic machine can simulate another. In this paper we shall look at the question of how fast a probabilistic machine can simulate another. This approach should be of interest in its own right, in view of the great attention that probabilistic algorithms have recently attracted.

A Direct Formulation And Computer-Implementation Of A Symbolic Network Analysis Algorithm, Timothy James Knerr

Electrical & Computer Engineering Theses & Dissertations

An algorithm for the symbolic analysis of linear, time-invariant, active or passive networks is presented. The algorithm incorporates the best features of earlier numerical and topological methods of symbolic analysis. A hybrid set of equations is formulated for a closed linear graph and arranged in matrix form. A numerical evalu­ation procedure for the determinant of this hybrid matrix results in an efficient method of symbolic analysis. A proof of the algorithm based on determinant evaluation by a permutation product expansion provides insight into relationships with other methods of symbolic analysis. A computer program implementation of the algorithm is described and …

Algorithms For Pipe Network Analysis And Their Reliability, Don J. Wood

KWRRI Research Reports

Algorithms for analyzing steady state flow conditions in pipe networks are developed for general applications. The algorithms are based on both loop equations expressed in terms of unknown flowrates and node equations expressed in terms of unknown grades. Five methods, which represent those in significant use today, are presented. An example pipe network is analyzed to illustrate the application of the various algorithms. The various assumptions required for the different methods are presented and the methods are compared within a common framework.

The reliabilities of these commonly employed algorithms for pipe network analysis are investigated by analyzing a large number …

A Dimensionality Reduction Algorithm For The Karhunen Loeve Transform, Salomi T. Charalambous

Computational Modeling & Simulation Engineering Theses & Dissertations

The Karhunen Loeve Transform has conclusively been shown to be the optimum data compression algorithm for signals belonging to the same second order stationary process. Consequently, researchers have been searching for a fast implementation for the transform. Fast imple­mentation methods similar to those developed for other orthogonal transforms are generally not applicable to the Karhunen Loeve Transform (KLT). Also, since the basis vectors composing the transformation matrix of the KLT are the eigenvectors of the covariance matrix of the input process, they must be computed first. The research re­ ported here is an attempt to reduce the dimensionality of the …

Comparative Schematology And Pebbling With Auxiliary Pushdowns, Nicholas J. Pippenger

All HMC Faculty Publications and Research

This paper has three claims to interest. First, it combines comparative schematology with complexity theory. This combination is capable of distinguishing among Strong's “languages of maximal power,” a distinction not possible when comparative schematology is based on computability considerations alone, and it is capable of establishing exponential disparities in running times, a capability not currently possessed by complexity theory alone. Secondly, this paper inaugurates the study of pebbling with auxiliary pushdowns, which bears to plain pebbling the same relationship as Cook's study of space-bounded machines with auxiliary pushdowns bears to plain space-bounded machines. This extension of pebbling serves as the …

Determiningeons : A Computer Program For Approximating Lie Generators Admitted By Dynamical Systems, Gregory G. Nagao

University of the Pacific Theses and Dissertations

As was recognized by same of the most reputable physicists of the world such as Galilee and Einstein, the basic laws of physics must inevitably be founded upon invariance principles. Galilean and special relativity stand as historical landmarks that emphasize this message. It's no wonder that the great developments of modern physics (such as those in elementary particle physics) have been keyed upon this concept.

The modern formulation of classical mechanics (see Abraham and Marsden [1]) is based upon "qualitative" or geometric analysis. This is primarily due to the works of Poincare. Poincare showed the value of such geometric analysis …

An Algorithm For The Electromagnetic Scattering Due To An Axially Symmetric Body With An Impedance Boundary Condition, F. Stenger, M. Hagmann, J. Scheing

Computer Science Faculty Publications

Let B be a body in R³, and let S denote the boundary of B. The surface S is described by S = {(x, y, z): (x² + Y²)^½= ƒ(z), -1≤ z ≤ I}, where ƒ analytic function that is real and positive on (-1, 1) and ƒ(±1) = 0. An algorithm is described for computing the scattered field due to a plane wave incident field, under Leontovich boundary conditions. The Galerkin method of solution used here leads to a block diagonal matrix involving 2M …

An Efficient Dft Algorithm Using The Walsh Transform, Albert P. Gerheim

Electrical & Computer Engineering Theses & Dissertations

The matrix transformation relating the sequency and frequency domains is derived. It is shown that these­ frequency-to-frequency conversion can be performed via a computationally efficient sparse matrix algorithm. The sequency-to-frequency algorithm can be used with a fast Hadamard transform to implement a discrete Fourier trans­ form. The efficiencies of this combined algorithm and a radix-two fast Fourier transform are compared.

The algorithm is applied to the sequency domain de­ sign of a Wiener digital filter. Improved computational efficiencies are achieved relative to the procedure de­veloped by Kahveci and Hall (9).

An Algorithm For Finding All Isomorphisms Of Two Graphs, Atanas Radenski

Mathematics, Physics, and Computer Science Faculty Articles and Research

No abstract provided.