Digital Commons Network^™

Mesh And Pyramid Algorithms For Iconic Indexing, Alok Choudhary, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

In this paper parallel algorithms on meshes and pyramids for iconic indexing are presented. Our algorithms are asymptotically superior to previously known parallel algorithms.

Load Redistribution On Hypercubes In The Presence Of Faults, Sanjay Ranka, Jhy-Chun Wang

Electrical Engineering and Computer Science - Technical Reports

In this paper, we present load redistribution algorithms for hypercubes in the presence of faults. Our algorithms complete in low-order polynomial of the number of faulty nodes and exhibit excellent experimental performance. These algorithms are topology independent and can be applied to a wide variety of networks.

A Logic For Natural Language, William C. Purdy

Electrical Engineering and Computer Science - Technical Reports

This paper describes a language called £N whose structure mirrors that of natural language. £N is characterized by absence of variables and individual constants. Singular predicates assume the role of both individual constants and free variables. The role of bound variables is played by predicate functors called "selection operators." Like natural languages, £N is implicitly many-sorted. £N does not have an identity relation. Its expressive power lies between the predicate calculus without identity and the predicate calculus with identity. The loss in expressiveness relative to the predicate calculus with identity however is not significant. Deduction in £N is intended to …

Techniques For Cubic Algebraic Surfaces I, Thomas W. Sederberg

Faculty Publications

The tutorial presents some tools for free-form modeling with algebraic surfaces, that is, surfaces that can be defined using an implicit polynomial equation f(x, y, z )=0. Cubic algebraic surfaces (defined by an implicit equation of degree 3) are emphasized. While much of this material applies only to cubic surfaces, some applies to algebraic surfaces of any degree. This area of the tutorial introduces terminology, presents different methods for defining and modeling with cubic surfaces, and examines the power basis representation of algebraic surfaces. Methods of forcing an algebraic surface to interpolate a set of points or a space curve …

Visual Speech Training Aid For The Deaf, Subhashri Venkat

Electrical & Computer Engineering Theses & Dissertations

A computer-based vowel articulation training aid has been developed. A "continuous" acoustic-phonetic transformation is performed to map speech parameters to a lower dimensionality display space. There are two possible approaches to this transformation problem. The transformation could be either linear or a combination nonlinear/linear. The nonlinear transformation is performed using a multi-layered feedforward neural network with linear output layers. Speech parameters are extracted either from an analog filter bank arrangement (band energies) or by a digital signal processing procedure (Discrete Cosine Transform Coefficients). The speech parameters obtained from both methods correspond to the spectral envelope of the speech signals. The …

Encoding Phonetic Knowledge For Use In Hidden Markov Models Of Speech Recognition, Danming Qian

Electrical & Computer Engineering Theses & Dissertations

Hidden Markov models (HMM's) have achieved considerable success for isolated-word speaker-independent automatic speech recognition. However, the performance of an HMM algorithm is limited by its inability to discriminate between similar sounding words. The problem arises because all differences between speech patterns are treated as equally important. Thus the algorithm is particularly susceptible to confusions caused by phonetically-irrelevant differences. This thesis presents two types of preprocessing schemes as candidates for improving HMM performance. The aim is to maximize the differences between phonologically-distinct speech sounds while minimizing the effect of variations in phonologically-equivalent speech sounds. The preprocessors presented are a discrete cosine …

A Simpler Proof Of Ph C Bp[Өp], Kenneth W. Regan, James S. Royer

Electrical Engineering and Computer Science - Technical Reports

We simplify the proof by S. Toda [Tod89] that the polynomial hierarchy PH is contained in BP[ӨP]. Our methods bypass the technical quantifier interchange lemmas in the original proof, and clarify the counting principles on which the result depends. We also show that relative to a random oracle R, PHR is strictly contained in ӨPR.

Taxonomic Reasoning And Lexical Semantics, William C. Purdy

Electrical Engineering and Computer Science - Technical Reports

Taxonomic reasoning is used in many applications, including many-sorted logic, knowledge bases, document retrieval, and natural language processing. These various applications have been dealt with independently. Because they have so much in common, a general approach to taxonomic reasoning would seem to be justified. This paper presents a theory of lexical semantics as an example of such a general approach. The theory defines a representation and an algebra for that representation. The operations of the algebra are inherently parallel, making them well matched to the capabilities of modern computer systems.

Parallel Implementation Of A Recursive Least Squares Neural Network Training Method On The Intel Ipsc/2, James Edward Steck, Bruce M. Mcmillin, K. Krishnamurthy, M. Reza Ashouri, Gary G. Leininger

Computer Science Faculty Research & Creative Works

An algorithm based on the Marquardt-Levenberg least-square optimization method has been shown by S. Kollias and D. Anastassiou (IEEE Trans. on Circuits Syst. vol.36, no.8, p.1092-101, Aug. 1989) to be a much more efficient training method than gradient descent, when applied to some small feedforward neural networks. Yet, for many applications, the increase in computational complexity of the method outweighs any gain in learning rate obtained over current training methods. However, the least-squares method can be more efficiently implemented on parallel architectures than standard methods. This is demonstrated by comparing computation times and learning rates for the least-squares method implemented …

Consistency And Generalization In Incrementally Trained Connectionist Networks, Tony R. Martinez

Faculty Publications

This paper discusses aspects of consistency and generalization in connectionist networks which learn through incremental training by examples or rules. Differences between training set learning and incremental rule or example learning are presented. Generalization, the ability to output reasonable mappings when presented with novel input patterns, is discussed in light of the above learning methods. In particular, the contrast between humming distance generalization and generalizing by high order combinations of critical variables is overviewed. Examples of detailed rules for an incremental learning model are presented for both consistency and generalization constraints.

A Direct Access Method Using A Neural Network Model, John William Meyer, George Winston Zobrist

Computer Science Technical Reports

One of the concerns in computer science involves optimizing usage of machines to make them more efficient and cost effective. One item of particular concern is the use of secondary storage devices, devices that store data other than in the main memory of the computer to which it is attached. The times for searching for data on these devices consistently proves to be a contributing factor in inefficient computer usage.

One data access method that avoids searching when possible is the hashing method. A function is defined to return the record number of a record based on its key field. …

Input Data Pattern Encoding For Neural Net Algorithms, Hyeoncheol Kim, George Winston Zobrist

Computer Science Technical Reports

First, a brief overview of neural networks and their applications are described, including the BAM (Bidirectional Associative Memory) model.

A bucket-weight-matrix scheme is proposed, which is a data pattern encoding method that is necessary to transform a set of real-world numbers into neural network state numbers without losing the pattern property the set has. The scheme is designed as a neural net so that it can be combined with other data processing neural nets. The net itself can be used as a bucket-sorting net also. This shows that traditional data structure problems can be an area that neural networks may …

Algorithms And Probabilistic Bounds For The Chromatic Number Of Random Composite Graphs, Jack L. Oakes, Billy E. Gillett

Computer Science Technical Reports

The composite graph coloring problem (CGCP) is a generalization of the standard graph coloring problem (SGCP). Associated with each vertex is a positive integer called its chromaticity. The chromaticity of a vertex specifies the number of consecutive colors which must be assigned to it.

An exact algorithm for solving the CGCP is presented. The algorithm is a generalization of the vertex-sequential with dynamic reordering approach for the SGCP. It is shown that the method is as effective on composite graphs as its counterpart is on standard graphs. Let X̅(CG_np) and X̅(SG_np) denote, respectively, the mean chromatic …

Monotone Logic Programming, Howard A. Blair, Allen Brown Jr., V. S. Subrahmanian

Electrical Engineering and Computer Science - Technical Reports

We propose a notion of an abstract logic. Based on this notion, we define abstract logic programs to be sets of sentences of an abstract logic. When these abstract logics possess certain logical properties (some properties considered are compactness, finitariness, and monotone consequence relations) we show how to develop a fixed-point, model-state-theoretic and proof theoretic semantics for such programs. The work of Melvin Fitting on developing a generalized semantics for multivalued logic programming is extended here to arbitrary abstract logics. We present examples to show how our semantics is robust enough to be applicable to various non-classical logics like temporal …

Korean Character Recognition Using Neural Networks, Jinhwan Koh, G. S. Moon, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

We present a neural-network approach for recognizing printed Korean characters. Our approach is based on a variant of the back-propagation algorithm. The results indicate that by transforming the character data into Hough space, we can achieve excellent recognition.

A Logic Grammar Foundation For Document Representation And Document Layout, Allen Brown Jr., Howard A. Blair

Electrical Engineering and Computer Science - Technical Reports

We present a powerful grammar-based paradigm for electronic document markup: coordinated definite clause translation grammars. This markup is of a declarative character, being, in effect, a collection of constraints on the logical and physical structure of documents. To the best of our knowledge, coordinated grammars and their parsers can accommodate all of the descriptive and layout processing functionality enjoyed by extant electronic markup languages. We describe an operational prototype that demonstrates the feasibility of a syntax-directed basis for formalizing and realizing document layout.

On Choosing An Optimally Trimmed Mean, Kishan Mehrotra, Paul Jackson, Anton Schick

Electrical Engineering and Computer Science - Technical Reports

In this paper we revisit the problem of choosing an optimally trimmed mean. This problem was originally addressed by Jaeckel (1971). We propose alternatives to Jaeckel's estimator and its modifications discussed in Andrews et al. (1972). Jaeckel's procedure chooses the optimal trimming by minimizing an estimate of the asymptotic variance of the trimmed mean. We use the bootstrap procedure to choose the optimal trimming. A simulation study shows that our procedure compares favorably with Jaeckel's procedure. We also discuss modification of our procedure to the two sample setting.

A Lexical Extension Of Montague Semantics, William C. Purdy

Electrical Engineering and Computer Science - Technical Reports

This paper presents a model theory of lexical semantics that is compatible with theories in the Montagovian tradition. Lexical expressions are modeled as subsets or “subspaces” in a “semantic spaces”. A unique representation is defined for subspaces of the semantic space. This unique representation is called the "normal form" of the lexical denotation. A Boolean algebra of normal forms is developed, in which lexical entailment is Boolean inclusion. The presentation in the body of the paper is informal, making use of examples to illustrate the theory and to indicate the range of applicability. Formal definitions and proofs in support of …

A Neural Network Simulator For The Connnection Machine, N. Asokan, Ravi V. Shankar, Chilukuri K. Mohan, Kishan Mehrotra, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

In this paper we describe the design, development, and performance of a neural network simulator for the Connection Machine (CM)3. The design of the simulator is based on the Rochester Connectionist Simulator(RCS). RCS is a simulator for connectionist networks developed at the University of Rochester. The CM simulator can be used as a stand-alone system or as a high-performance parallel back-end to RCS. In the latter case, once the network has been built by RCS, the high-performance parallel back-end system constructs an equivalent network on the CM processor array and executes it. The CM simulator facilitates the exploitation of the …

Dynamic Range Partitioning In Multiprocessor Database Implementations, Ophir Frieder

Electrical Engineering and Computer Science - Technical Reports

Multiprocessor implementation of the relational database operators has recently received great attention in literature [1-4, 8, 11]. As the complexity of implementing the relational operators rests on the inter-node communication patterns involved in an operation, greater research attention has been focused on Join algorithms. The Join traffic patterns subsume those of the remaining relational operators. To effectively exploit parallelism in bucket based join implementations, the domain of the joining attributes must be partitioned into equal subranges. That is, the processing of each subrange requires roughly the same amount of time. A skewed distribution of workload significantly hinders performance. As relations …

Forecasting Sunspot Numbers Using Neural Networks, Ming Li, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

A recurrent connectionist network has been designed to model sunspot data. Preliminary experimental work shows that the network can produce competitive results as compared to traditional autoregressive models. The method is not problem specific and could be applied to other problems in dynamical system modeling, recognition, prediction, and control fields. It is observed that statistical methods can be used to design an appropriate neural network architecture.

Simplifications To "A New Approach To The Covering Radius...”, H. F. Mattson Jr

Electrical Engineering and Computer Science - Technical Reports

We simplify the proofs of four results in [3], restating two of them for greater clarity. The main purpose of this note is to give a brief transparent proof of Theorem 7 of [3], the main upper bound of that paper. The secondary purpose is to give a more direct statement and proof of the integer programming determination of covering radius of [3]. Theorem 7 of [3] follows from a simple result in [2], which we state with the notation (for the linear code A).

Arrays And The Lambda Calculus, Klaus Berkling

Electrical Engineering and Computer Science - Technical Reports

Why do functional languages have more difficulties with arrays than procedural languages? The problems arising in the designing of functional languages with arrays and in their implementations are manifold. They can be classified according to 1) first principles, 2) semantics, 3) pragmatics, and 4) performance. This paper attempts to give an outline of the issues in this area, and their relation to the lambda calculus. The lambda calculus is a formal system and as such seemingly remote from practical applications. However, specific representations and implementations of that system may be utilized to realize arrays such that progress is made towards …

Optical Switching And Routing Architectures For Fiber-Optic Computer Communication Networks, Alok Choudhary, Salim Hariri, Wang Song, Partha Banerjee, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

Optical technology has become a significant part of communication networks. We propose an Optical Interface Message Processor (OPTIMP) that exploits high-bandwidth, parallelism, multi-dimensional capability, and high storage density offered by optics. The most time consuming operations such as switching and routing in communication networks are performed in optical domain in the proposed system. Our design does not suffer from the optical/electrical conversion bottlenecks and can perform switching and routing in the range of Gigabits/s. The proposed design can have significant impact in high-speed communication networks as well as high-speed interconnection networks for parallel computers. The source-destination (S-D) information from a …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, May 1990, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A four page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

Strong Completeness Results For Paraconsistent Logic Programming, Howard A. Blair, V. S. Subrahmanian

Electrical Engineering and Computer Science - Technical Reports

In [6], we introduced a means of allowing logic programs to contain negations in both the head and the body of a clause. Such programs were called generally Horn programs (GHPs, for short). The model-theoretic semantics of GHPs were defined in terms of four-valued Belnap lattices [5]. For a class of programs called well-behaved programs, an SLD-resolution like proof procedure was introduced. This procedure was proven (under certain restrictions) to be sound (for existential queries) and complete (for ground queries). In this paper, we remove the restriction that programs be well-behaved and extend our soundness and completeness results to apply …

Interactive Morphometrics From Three-Dimensional Surface Images, William A. Barrett, Shawn C. Becker

Faculty Publications

Techniques have been developed for extracting three-dimensional (3D) measurements directly and interactively from 3D representations of surface anatomy. In order to obtain 3D measurements the anatomical surface is interrogated directly through the use of morphometric tools. Morphometric tools include points, 3D graphical "probes", and logical sectioning functions which interact with the surface through depth buffer compositing operations. Tools are interactively positioned on or through the surface to measure surface dimensions and partial volumes, or to define intersecting functions which allow surface anatomy to be visualized in the context of surrounding anatomy. Visualization is also enhanced because tools reveal much pertaining …

A Proof For A Quickhull Algorithm, Jonathan Scott Greenfield,

Electrical Engineering and Computer Science - Technical Reports

The planar convex hull problem is fundamental to computational geometry and has many applications, including pattern recognition and image processing. QuickHull is a simple planar convex hull algorithm analogous to Hoare’s QuickSort [1]. This paper presents a pedagogical description and analysis of a QuickHull algorithm, along with a formal proof of correctness.

Michigan Apple Pest Identifier And Manager Expert System, James R. Schalk

Masters Theses

The Michigan Apple Pest Identifier and Management System (MAPI) is a knowledge- based consultation software system. MAPI was designed to provide the user with the ability to identify insects which may harm the apples of Michigan orchards and to project occurrences of maximum adult emergence. A discussion of standard entomological and expert system concepts and the application of these concepts to the processing of information by the Michigan Apple Pest Identifier and Management System is presented. Future possible expansions of the system are suggested.

Introductory Dataperfect® Instruction, Frances Jenson Larsen

Theses and Dissertations

The project should be used in a beginning computer class. These units contain projects from simple to complex. The first instructional unit uses a database that comes with the DataPerfect® program. The students build and manipulate a small database. Reports are prepared, and finally the students design an original database. These instructional units are intended to be used in a high school classroom with the DataPerfect® computer program. DataPerfect® is a copyrighted program marketed by WordPerfect Corporation of Orem, Utah.