Engineering Commons^™

Dna Mapping Algorithms: Clone Sequencing, Judith H. Lewis, Will Gillett

All Computer Science and Engineering Research

The DNA restriction mapping problem can be abstracted to the Shortest Common Matching String problem by viewing the restriction fragment lengths as symbols and the clones as bags. The Shortest Common Matching String problem can be decomposed into the Bag Sequencing problem and the Symbol Sequencing problem. All three of these problems have bene shown to be NP-hard. Rhee has proposed a family of greedy algorithms to compute polynomial time approximations to the Bag Sequencing problem, which produced surprisingly good performance results on abstracted data. In the test data generated by Rhee for pragmatic analysis, the symbols in bags represented …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 7, Number 6, September 1991, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

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

Converting Binary Thresholds Networks Into Equivalent Symmetric Networks, Gadi Pinkas

All Computer Science and Engineering Research

We give algorithms to convert any network of binary threshold units (that does not oscillate) into an equivalent network with symmetric weight matrix (like Hopfield networks [Hopfield 82] or Boltzmann machines [Hinton, Sejnowski 88]). The motivation for the transformation is dual: a) to demonstrate the expressive power of symmetric networks; i.e. binary threshold networks (that do not oscillate) are subsumed in the energy minimization paradigm; 2) to use network modules (developed for the spreading activation paradigm for example), within the energy minimization paradigm. Thus optimization [Tank, Hopfield 88] and approximation of hard problems can be combined with efficient modules, that …

Composition, Superposition, And Encapsulation In The Formal Specification Of Distributed Systems, Kenneth J. Goldman

All Computer Science and Engineering Research

Composition, superposition, and encapsulation are important techniques that work well together for designing large distributed software systems. Composition is a symmetric operator that allows system components to communicate with each other across module boundaries. Superposition is an asymmetric relationship that allows one system component to observe the state of another. Encapsulation is the ability to define the reason about the behavior of a module in terms of a well-defined boundary between that module and its environment, while hiding the internal operations of that module. In this paper, the I/O automation model of Lynch and Tuttle is extended to permit superposition …

The Spectrum Simulation System: A Formal Approach To Distributed Algorithm Development Tools, Kenneth J. Goldman

All Computer Science and Engineering Research

We present the Spectrum Simulation System, a new research tool for the design and study of distributed algorithms. Based on the formal Input/Output Automation model of Lynch and Tuttle, Spectrum allows one to express distributed algorithms as collections of I/O automata and simulate them directly in terms of the semantics of that model. This permits integration of algorithm specification, design, debugging, analysis, and proof of correctness within a single formal framework that is natural for describing distributed algorithms. Spectrum provides a language for expressing algorithms as I/O automata, a simulator for generating algorithm executions, and a graphics interface for constructing …

An Access Protection Solution For Heavy Load Unfairness In Dqdb, Lakshmana N. Kumar, Andreas D. Bovopoulos

All Computer Science and Engineering Research

This paper discusses the unfairness issue arising in a 802.6 DQDB network at high loads-- when the traffic demand to a bus exceeds the capacity of that bus. As per the 802.6 protocol, at heavy loads, the end nodes along a bus experience longer delays than the other nodes. The origin and remedy of this heavy load unfairness is discussed. An access control scheme is proposed as a solution. The comparison of the proposed scheme with 802.6 protocol is presented. The simulation results and performance characteristics are discussed under several types of loads. With symmetric load conditions under the proposed …

Center For Computer And Information Sciences Master Of Science In Computer Science Summer Courses 1991, Nova Southeastern University

College of Engineering and Computing Course Catalogs

No abstract provided.

Center For Computer And Information Sciences Master Of Science In Computer Information Systems Summer Courses 1991, Nova Southeastern University

College of Engineering and Computing Course Catalogs

No abstract provided.

Rapid Display Of Radiographic Images, Jerome R. Cox Jr., Stephen M. Moore, Robert A. Whitman, G. James Blaine, R. Gilbert Jost, L. Magnus Karlsson, Thomas L. Monsees, Gregory L. Hansen, Timothy C. David

All Computer Science and Engineering Research

The requirements for the rapid display of radiographic images exceed the capabilities of widely available display, computer and communication technologies. Computed radiography captures data with a resolution of about four megapixels. Large format displays are available that can present over four megapixels. One megapixel displays are practical for use in combination with large format displays and in areas where the viewing task does not require primary diagnosis. This paper describes an electronic radiology system that approximates the highest quality systems, but through the use of several interesting techniques allows the possibility of its widespread installation throughout hospitals. The techniques uses …

A Prolog System For Converting Vhdl-Based Models To Generalized Extraction System (Ges) Rules, Michael A. Dukes, Frank M. Brown, Joanne E. Degroat

AFIT Documents

With the advent of VHDL accurate documentation of hardware designs is a practical reality. In the past, schematics were typically used for documentation of hardware designs. However, these schematics would usually become obsolete as the hardware design was being constructed. Deviations in the hardware design would sometimes not be reflected in the schematics. For design groups, failure to update schematics could lead to different parts of a hardware design becoming incompatible. A system to ensure compliance of hardware with its VHDL documentation is presented in this paper. The system, vhdl2ges, is meant to help guide the development of hardware by …

Dna Mapping Algorithms: Abstract Data Types - Concepts And Implementation, Will Gillett, Liz Hanks

All Computer Science and Engineering Research

The conceptual aspects of and the implementation details of a set of self-identifying abstract data types (ADT) are described. Each of the ADTs constitutes a specific class of object, upon which a set of well-defined access functions is available. The intent of these ADTs is to supply a paradigm in which a class of object is available for manipulation, but in which the underlying implementation is hidden from the application programmer. Specific ADTs are the described in some detail. The tagged architecture used to achieve the self-identifying property of the ADTs is presented, and a set of required system-backbone access …

The Difficulty Of Random Attribute Noise, Sally A. Goldman, Robert H. Sloan

All Computer Science and Engineering Research

This paper studies the robustness of pac learning algorithms when the instance space is {0,1}n, and the examples are corrupted by purely random noise affecting only the instances (and not the labels). In the past, conflicting results on this subject have been obtained-- the "best agreement" rule can only tolerate small amounts of noise, yet in some cases large amounts of noise can be tolerated. We show the truth lies somewhere between the two alternatives. For uniform attribute noise, in which each attribute is flipped independently at random with the same probability, we present an algorithm that pac learns monomial …

Computational Learning Theory Lecture Notes For Cs 582 Spring Semester, 1991, Sally A. Goldman

All Computer Science and Engineering Research

This manuscript is a compilation of lecture notes from the graduate level course CS 582, "Computational Learning Theory," I taught at Washington University in the spring of 1991. Students taking the course were assumed to have background in the design and analysis of algorithms as well as good mathematical background. Given that there is no text available on this subject, the course material was drawn from recent research papers. I selected the first twelve topics and the remainder were selected by the students from a list of provided topics. This list of topics is given at the end of these …

Low To Medium Level Image Processing For A Mobile Robot, Cecilia H. Espinosa

Dissertations and Theses

The use of visual perception in autonomous mobile systems was approached with caution by mobile robot developers because of the high computational cost and huge memory requirements of most image processing operations. When used, the image processing is implemented on multiprocessors or complex and expensive systems, thereby requiring the robot to be wired or radio controlled from the computer system base.

Hereby developed is a simple, inexpensive and automatic image processing subsystem that is completely implementable on a PC-386SX with 640K base memory. The subsystem will serve as the front end of the vision system for the PSUBOT, an autonomous …

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

BITs and PCs Newsletter

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

Applying Formal Verification Methods To Pure Rule-Based Programs, Rose F. Gamble, Gruia-Catalin Roman, William E. Ball, H. Conrad Cunningham

All Computer Science and Engineering Research

Reliability, defined as the guarantee that a program satisfies its specifications, is an important aspect of many applications for which rule-based expert systems are suited. Verification refer to the process used to determine the reliability of the rule-based program. Because past approaches to verification are informal, guarantees of reliability cannot fully be made without severely restricting the system. On the other hand, by constructing formal specifications for a program and showing the program satisfies those specifications, guarantees of reliability can be made. This paper presents an assertional approach to the verification of rule-based programs. The proof logical needed for verification …

Hybrid Wafer Scale Microcircuit Integration -- [ 5008213 ], Edward S. Kolesar Jr.

AFIT Patents

A wafer scale integration arrangement wherein integrated circuit die of varying size, fabrication processes, and function are commonly mounted in the same host wafer using a filled epoxy material of special characteristics. The mounting epoxy material also serves as a substrate for the die interconnecting conductors in regions adjacent the mounted die. The described assembly also includes a newly available photosensitive polyimide material as a planarization and passivation covering for the die and hose wafer and as a mounting surface for an interconnecting metal conductor array. Multiple levels of interconnection metal. Fabrication processes for the die to host wafer attachment …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, April 1991, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

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

Center For Computer And Information Sciences Master Of Science In Computer Science Spring 1991, Nova Southeastern University

College of Engineering and Computing Course Catalogs

No abstract provided.

An Improved Method For Online Calculation And Compensation Of The Static Deflection At A Robot End-Effector, Paul P. Lin, Hsiang-Dih Chiang, Xiu Xun Cui

Mechanical Engineering Faculty Publications

Traditionally, robotic deflection analysis for a low-weight robot has been performed based on an assumption that each link is treated as a cantilever beam, which leads to no angular deflection at a joint. In practice, a robotic intermediate joint is linearly and angulary deflected when a load is applied at the end-effector. It is found in this study that the additional link deflection resulting from the angular deflection of a robotic revolute joint substantially contributes to the end-effector's total deflection. This article presents an improved method via a combination of classical beam theory, energy methods and the concepts of differential …

Simulator For Concurrent Processing Data Flow Architectures, Mahyar R. Malekpour

Electrical & Computer Engineering Theses & Dissertations

A software simulator capable of simulating execution of an algorithm graph on a given system under the Algorithm To Architecture Mapping Model (ATAMM) rules is presented in this thesis. ATAMM is capable of modeling the execution of large-grained algorithms on distributed data flow architectures. Investigating the behavior and determining the performance of an ATAMM based system requires the aid of software tools. The ATAMM Simulator presented in this thesis is capable of determining the behavior, performance, and reliability of a system without having to build a hardware prototype. Case studies are performed on four algorithms to demonstrate the capabilities of …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, March 1991, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

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

A Prolog-Based System For Hardware Verification, Kevin L. Sparks

Theses and Dissertations

With the expanding number of components provided on a single digital chip, verification of digital designs is becoming a major problem. The more circuits one places on a single chip, the greater the number of input/output combinations which need to be checked. A paper by Barrow in 1984 discusses a Prolog-based hierarchical formal verification system which he calls VERIFY. Barrow provided a lot of information on what VERIFY can and cannot do, and on projected enhancements. He does not, however, mention how VERIFY actually performs the task of formal verification. This thesis will provide a description of one possible implementation …

A Common Interface Real-Time Multiprocessor Operating System For Embedded Systems, Michael S. Rottman

Theses and Dissertations

Large real time applications such as aerospace avionics systems, battle management, and factory automation place many demands and constraints on the computing system not found in other applications. Software development is hindered by software dependence on the computer architecture and the lack of portability between systems. This thesis specifies and designs a real time multiprocessor operating system (RTMOS) that implements a consistent programming model, enabling the development of real time parallel software independent of the target architecture. The RTMOS defines the core functionality required to demonstrate the programming model. The RTMOS functional requirements are specified using Structured Analysis and Design …

Dna Mapping Algorithms: Topological Mapping, Kenneth Moorman, Paul Poulosky, Will Gillett

All Computer Science and Engineering Research

There are several basic approaches that can be used in attempting to produce high-resolution DNA restriction maps. A standard approach is the match/merge approach in which first the topology of the map units being mapped together is suppressed and lists of potential matches between fragments are generated, and second the topology is introduced to eliminate matchlists which are inconsistent with the topology. This technical report documents a different approach to DNA mapping, known as topological mapping. In topological mapping the precedence of the two criteria are reversed, i.e., the topology of the two map units is used as the primary …

Optimal Iterative Task Scheduling For Parallel Simulations, Joann M. Sartor

Theses and Dissertations

The ultimate purpose of this research is to reduce the time needed for execution of parallel computer simulations. In particular, the impact of task assignment strategies is determined for parallel VHDL circuit simulations. The classical scheduling problem, which assigns n precedence-constrained tasks to m processors is NP-complete in all but the simplest cases. The problem of assigning simulation tasks is further complicated by the iterative nature of computer simulations: each task is required to execute multiple times as the simulation executes. This investigation develops a polynomial-time algorithm (the level strategy) which provides optimal assignment for iterative systems with specific constraints. …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, February 1991, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

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

Performance Evaluation Of A Traffic Control Mechanism For Atm Networks, Andreas D. Bovopoulos

All Computer Science and Engineering Research

Future ATM networks will be required to support a plethora of services, transaction types and cell sequence behaviors with performance guarantees. Before this goal can be realized, however, some basically problems related to bandwidth allocation and traffic control in the ATM layer must be resolve. Such problems will in all likelihood defy solution as long as they studied in isolation without a unifying traffic characterization and traffic control framework. This work presented in this paper is part of an ongoing effort directed at the development of an integrated traffic characterization and control infrastructure for ATM networks. In this paper a …

Saam: The Strategic Asset Allocation Model, Judy Lewis, Todd Gamble, John Tai

All Computer Science and Engineering Research

Asset Allocation has become a dominant factor for investment strategies in recent years. It has found that by holding a strategically diversified portfolio, a high total return on investments can be maintained while, at the same time, reducing portfolio volatility. With recent federal regulations mandating pension investment responsibilities, appropriate asset allocation has become more important than ever. SAAM is a software package specifically designed to be used as a tool to aid the investment professional in determining pension portfolio allocations. SAAM uses the expect system shell CLIPS, has a user-friendly interface, displays output graphically, and runs within the confines of …

Performance Analysis Of The Ethernet Under Conditions Of Bursty Traffic, Tony Y. Mazraani, Gurudatta M. Parulkar

All Computer Science and Engineering Research

In this paper we present a simulation study of the Ethernet performance under conditions of bursty traffic. This study is motivated by two observations: Ethernet will continue to be a widely used Local Area Network (LAN), especially as an access LAN for future high speed internet (or Broadband ISDN); and future high speed applications can best be modeled as bursty sources. Bursty traffic in this study is specified using three parameters: peak bandwidth, average bandwidth, and burst factor. The simulation study shows that the inherent behavior of the Ethernet does not change with bursty traffic. That is, as long as …