Physical Sciences and Mathematics Commons^™

A Synthesis Technique Of General Petri Nets For Flexible Manufacturing And Multi-Rate Digital Signal Processing, Murthy S. Valluri

Theses

General Petri nets are useful for modeling flexible manufacturing system with multiple robots and workstations [KOH 90] and for multi-rate digital signal processing systems [CHA 91].. A problem of using Petri nets for modeling various systems is the large number of states generated. Various synthesis approaches have been proposed. Most of them do not deal with general Petri nets. Koh et. al. [KOH 90] invented a synthesis technique for generalized Petri nets. The purpose of this thesis is to extend their work by modifying the knitting technique by adding the Arc-Ratio rule.

Representation Of Graphical Deep Knowledge In An Object-Oriented Database System, Prasanna S. Venkatesh

Theses

Object-oriented approaches to the design of complex graphical interfaces have received an enormous impetus in the database and knowledge representation disciplines. As traditional CAD systems store information about all the objects for display purposes but do not store any knowledge for reasoning purposes, they are considered as "knowledge poor" and they cannot support efficient environments for design. In Artificial Intelligence the notion of "Graphical Deep Knowledge" has been proved successful to represent knowledge about objects for display purposes as well as reasoning purposes. To design "knowledge rich" systems which can support better graphical interfaces, the theory of "Graphical Deep Knowledge" …

A Study In Systems Integration Architecture, Sashidhar M. Prasad

Theses

This Thesis studies the two architectures OSCA and ANSA which support the ODPSE principle in the first two parts. In the third part the framework for integrating these two architectures is described. The idea of integration architectures in relation to open architectures is studied using the enabling technologies.

Communications Network For Distributed Real-Time Systems, Charles Silva

Theses

No abstract provided.

User Authentication And Related Topics: An Annotated Bibliography, Eugene H. Spafford, Stephen A. Weeber

Department of Computer Science Technical Reports

No abstract provided.

A Note On Many-One And 1-Truth-Table Complete Languages, Steven Homer, Stuart A. Kurtz, James S. Royer

Electrical Engineering and Computer Science - Technical Reports

The polynomial time 1-tt complete sets for EXP and RE are polynomial time many-one complete.

The Combinatorics Of Algebraic Splines, Chanderjit L. Bajaj

Department of Computer Science Technical Reports

No abstract provided.

Optimal Algorithms For Multipacket Routing Problems On Rings, Fillia Makedon, Antonios Symvonis

Computer Science Technical Reports

We study multipacket routing problems. We divide the multipacket routing problem into two classes, namely, distance limited and bisection limited routing problems. Then, we concentrate on rings of processors. We prove a new lower bound of 2n/ 3 routing steps for the case of distance limited routing problems. We also give an algorithm that tightens this lower bound. For bisection limited problems the lower bound is kn/ 4,k >2, where k is the number of packets per processor. The trivial algorithm needs in the worst case k | n /2| steps to terminate. An algorithm that completes the routing in …

Visualization Of Four Dimensional Space And Its Applications (Ph.D. Thesis), Jianhua Zhou

Department of Computer Science Technical Reports

No abstract provided.

An Efficient Neural Algorithm For The Multiclass Problem, Rangachari Anand, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

One connectionist approach to the classification problem, which has gained popularity in recent years, is the use of backpropagation-trained feed-forward neural networks. In practice, however, we find that the rate of convergence of net output error is especially low when training networks for multi-class problems. In this paper, we show that while backpropagation will reduce the Euclidean distance between the actual and desired output vectors, the difference between some of the components of these vectors will actually increase in the first iteration. Furthermore, the magnitudes of subsequent weight changes in each iteration are very small, so that many iterations are …

Efficient Maximum-Likelihood Soft-Decision Decoding Of Linear Block Codes Using Algorithm A, Yunghsiang S. Han, Carlos R.P. Hartmann, Chih-Chieh Chen

Electrical Engineering and Computer Science - Technical Reports

In this report we present a novel and efficient maximum-likelihood soft-decision decoding algorithm for linear block codes. The approach used here is to convert the decoding problem into a search problem through a graph which is a trellis for an equivalent code of the transmitted code. Algorithm A*, which uses a priority-first search strategy, is employed to search through this graph. This search is guided by an evaluation function f defined to take advantage of the information provided by the received vector and the inherent properties of the transmitted code. This function f is used to drastically reduce the search …

Parallel Divide And Conquer, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

We develop a generic divide and conquer algorithm for a parallel tree machine. From the generic algorithm we derive balanced, parallel versions of quicksort and the fast Fourier transform by substitution of data types, variables and statements. The performance of these algorithms is analyzed and measured on a Computing Surface configured as a tree machine with distributed memory.

Do Hypercubes Sort Faster Than Tree Machines?, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

We develop a balanced, parallel quicksort algorithm for a hypercube and compare it with a similar algorithm for a binary tree machine. The performance of the hypercube algorithm is measured on a Computing Surface.

The Fast Fourier Transform, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial discusses the fast Fourier transform, which has numerous applications in signal and image processing. The FFT computes the frequency components of a signal that has been sampled at n points in O( n log n) time. We explain the FFT and illustrate it by examples and Pascal algorithms. We assume that you are familiar with elementary calculus.

Design And Analysis Of Asynchronous Adders, Khalid Khanfar

Masters Theses

The aim of this study is to come up with a fast adder suitable for use in self-timed subsystems. 7 adders were evaluated.

The findings from this study indicated that a Conditional Sum Adder (CSA) is the best candidate for high speed addition. One of the two resulting adders was given the name High Speed Conditional Sum Adder (HSCSA) .

Specifying Interdatabase Dependencies In A Multidatabase Environment, Marek Rusinkiewicz, Amit P. Sheth, George Karabatis

Kno.e.sis Publications

The problem of interdatabase dependencies and the effect they have on applications updating interdependent data are addressed. A model that allows specifications of constraints among multiple databases in a declarative fashion is proposed. The separation of the constraints from the application programs facilitates the maintenance of data constraints and allows flexibility in their implementation. It allows investigation of various mechanisms for enforcing the constraints, independently of the application programs. By grouping the constraints together, it is possible to check their completeness and discover possible contradictions among them. The concepts of polytransactions, which use interdatabase dependencies to generate a series of …

Investigative Search Of Quality Historical Software Support Cost Data And Software Support Cost-Related Data, Brent L. Barber

Theses and Dissertations

The purpose of the study was to determine what software support cost data and software support cost-related data should and can be collected by the Air Force. In addition, the study was to determine how the subject data should be collected. The collection of this data is necessary in order to measure the accuracy and calibration requirements of the software support cost models used by the Air Force. The study found there was no standard set of data items, and no standard procedures in place for the collection of this data. In most cases data were available or easily accessible, …

Reducing Requirements Errors Through The Use Of Computer-Aided Software Engineering (Case) Tools And During Requirements Analysis, Marvin B. Key Jr.

Theses and Dissertations

This study investigated whether using CASE tools in the requirements analysis phase of software development reduced the software coding errors attributable to requirement analysis. A survey of the population gathered data as to the current practices and efforts in the use of CASE tools. The data was gathered in two groups: a control group and a sample group. The data was analyzed by group and in various combinations to obtain a greater understanding into population trends and tendencies. The results of the research indicate that the Air Force does not use CASE tools to any great extent. Also, error and …

Documentation Requirements For Software Maintenance, Timothy S. Mcarthur

Theses and Dissertations

This study investigated the requirement for documentation during the maintenance phase of the software life cycle. Without proper documentation, maintenance personnel are not able to effectively understand the design of a software system and spend many hours performing design recovery before any type of maintenance can be performed. A review of existing information showed a wide range of opinion among the experts in the field of software maintenance and was not conclusive. A survey of Air Force software maintenance personnel was then conducted to determine the need, availability, and tailoring results of the documents listed on DOD-STD 2167A. The analysis …

Face Recognition With The Karhunen-Loeve Transform, Pedro F. Suarez

Theses and Dissertations

The major goal of this research was to investigate machine recognition of faces. The approach taken to achieve this goal was to investigate the use of Karhunen-Loe've Transform (KLT) by implementing flexible and practical code. The KLT utilizes the eigenvectors of the covariance matrix as a basis set. Faces were projected onto the eigenvectors, called eigenfaces, and the resulting projection coefficients were used as features. Face recognition accuracies for the KLT coefficients were superior to Fourier based techniques. Additionally, this thesis demonstrated the image compression and reconstruction capabilities of the KLT. This theses also developed the use of the KLT …

Effect Of Spatial Locality Prefetching On Structural Locality, Dirk D. Schalch

Theses and Dissertations

The purpose of this research was to analyze the effect that spatial locality prefetching in cache memory has on the structural locality of program memory referencing behavior. To examine this, a software simulator was built to model a proposed two-level cache memory subsystem. The proposed subsystem was designed to use spatial locality prefetching to exploit the structural locality contained in executing computer workloads. New memory referencing models were developed to incorporate the combined use of structural locality and spatial locality prefetching. From these models, equations were derived to predict the hit rates for both caches. Combined with the state transition …

Three-Dimensional Medical Image Registration Using A Patient Space Correlation Technique, Patrick J. Rizzuto Jr.

Theses and Dissertations

The routine clinical use of three-dimensional data provided by modern medical imaging procedures is often impeded by the difficulty in accurately correlating the resultant volume datasets. These data are frequently obtained at different times using the same modality, or images of the same patient are sometimes produced using more than one imaging modality. In order to analyze the similarities and differences between such images, it is necessary for the medical imaging data to be spatially aligned using a process known as image registration. This research investigated a structure-based image registration technique based upon simple, three-dimensional relationships among user identified landmarks. …

Design Of Style-V — A Translator To Convert Standard Vhdl Into A Stylized Form For Automated Microcode Generation, Dennis A. Rumbley

Theses and Dissertations

This thesis provides an analysis and preliminary design of Style V, a source-to-source computer language translator. Style-V converts IEEE standard VHDL into a special style of VHDL defined for a commercial tool, the Integrated Design Automation System (IDAS). Thirteen mappings between standard VHDL and the IDAS subset were identified. The mappings were analyzed using Domain Analysis and Modern Structured Analysis techniques. Four processes covering several of the mappings were completely analyzed. One mapping to convert CASE statements to IF statements was implemented. Since the IDAS restricts designs to bit logic, a method for representing multilevel logic with bit logic was …

A Cache Design To Exploit Structural Locality, Curtis M. Winstead

Theses and Dissertations

A design and VHDL implementation of a content-addressable memory (CAM) to exploit structural locality is the subject of this research. The concept of structural locality is that memory locations are referenced in the same order as they were previously referenced. Therefore, if memory locations that exhibit structural locality can be made available to the CPU (Center Processing Unit) through a fast data store, an increase in speed of the computer system can be realized. The CAM's purpose is to store memory references in the order they were used by the CPU and prefetch these locations to a smaller on- chip …

Design And Application Of An Object Oriented Graphical Database Management System For Synthetic Environments, John A. Brunderman

Theses and Dissertations

The Air Force Institute of Technology (AFIT) is investigating the use of synthetic environments for military applications under the sponsorship of Rome Laboratories (RL). Areas under investigation include mission planning, battle management and flight simulation. The work reported in this thesis focuses on the object-oriented design and implementation of the Graphical Database Management System (GDMS) used to support research in these areas. GDMS provides the data structures, file format and algorithms to manage and render hierarchical, three-dimensional, polygonal models. Flexibility and adaptability were key factors in its design. A secondary objective of this research was to demonstrate the functionality of …

Analysis Of A Decision Support System For Case Tool Selection And The Specification Of An Ada To Sql Abstract Interface, Tina M. Deangelis

Theses and Dissertations

Information overload has long been a problem in the fast moving technical field of software development. Yet quality information is needed to make informed decisions about buying software tools that help in software development. Computer Aided Software Engineering (CASE) tools help to coordinate and control information in large software developments. Many CASE tool purchases, however, are being based on ad hoc tool evaluation and selection methods which depend on biased vendor information. To capture specific knowledge about how to pick a tool for a given software development effort, a historical database that identifies important tool characteristics needed to be maintained …

Design And Implementation Of A Graphical User Interface And Database Management System For The Saber Wargame, Andrew M. Horton

Theses and Dissertations

Saber is a theater level, multi-sided, airpower employment computerized wargame that can be programmed to simulate any combat scenario. The model simulates theater level combat between air and land forces, and takes into account the effects of logistics, resupply, and both theater nuclear and chemical warfare. The major objective of the Saber model is to provide a suitable educational platform to allow users to apply basic, tactical employment concepts to multiple combat units, each having a specialized mission, and incorporating every branch of the armed services. This thesis documents a graphical user interface and data management system that has been …

Enhanced Animation Of Parallel Algorithms, Michael D. Lack

Theses and Dissertations

Algorithm animation is a visualization method used to enhance understanding of the functioning of an algorithm or program. Visualization is used for many purposes, including education, algorithm research, performance analysis, and program debugging. This research, which follows from previous work, examines algorithm animation requirements for the various visualization purposes and extends the capabilities of an existing facilities, the AFIT algorithm Animation Research Facility (AAARF). The structure of AAARF is summarised and its visualization capabilities presented, analysed and compared with other similar packages. This research focuses on the parallel data requirements of the AAARF users, and the meaningful display of large …

Improved Task Scheduling For Parallel Simulations, Andrew E. Mcnear

Theses and Dissertations

The objective of this investigation is to design, analyze, and validate the generation of optimal schedules for simulation systems. Improved performance in simulation execution times can greatly improve the return rate of information provided by such simulations resulting in reduced development costs of future computer/electronic systems. Optimal schedule generation of precedence-constrained task systems including iterative feedback systems such as VHDL or war gaming simulations for execution on a parallel computer is known to be N P-hard. Efficiently parallelizing such problems takes full advantage of present computer technology to achieve a significant reduction in the search times required. Unfortunately, the extreme …

An Animated Graphical Postprocessor For The Saber Wargame, Gary W. Klabunde

Theses and Dissertations

One of the most cost effective ways to learn and home the skills necessary to conduct and win a war is through the use of realistic computer simulations of conflict, or wargames. The Saber wargame was developed for just this purpose. Saber is a multisided, theater-level simulation developed by the Air Force Institute of Technology for the Air Force Wargaming Center. It models conventional, nuclear, and chemical warfare between aggregated air and ground forces. To aid in the realism, the effects of logistics, satellites, weather, and intelligence are represented. Saber provides an avenue for senior level joint service officers to …