Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 15 of 15
Full-Text Articles in Physical Sciences and Mathematics
Dna Mapping Algorithms: Clone Sequencing, Judith H. Lewis, Will Gillett
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 …
An Access Protection Solution For Heavy Load Unfairness In Dqdb, Lakshmana N. Kumar, Andreas D. Bovopoulos
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 …
Converting Binary Thresholds Networks Into Equivalent Symmetric Networks, Gadi Pinkas
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
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
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 …
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
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 …
The Difficulty Of Random Attribute Noise, Sally A. Goldman, Robert H. Sloan
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
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 …
Dna Mapping Algorithms: Abstract Data Types - Concepts And Implementation, Will Gillett, Liz Hanks
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 …
Applying Formal Verification Methods To Pure Rule-Based Programs, Rose F. Gamble, Gruia-Catalin Roman, William E. Ball, H. Conrad Cunningham
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 …
Dna Mapping Algorithms: Topological Mapping, Kenneth Moorman, Paul Poulosky, Will Gillett
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 …
Saam: The Strategic Asset Allocation Model, Judy Lewis, Todd Gamble, John Tai
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
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 …
Performance Evaluation Of A Traffic Control Mechanism For Atm Networks, Andreas D. Bovopoulos
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 …
Transforming A Rule-Based Program, Rose F. Gamble
Transforming A Rule-Based Program, Rose F. Gamble
All Computer Science and Engineering Research
Conflict resolution is a form of global control used in production systems to achieve an efficient sequential execution of a rule-based program. This type of control is not used to parallel production system models [6,13]. Instead, only those programs that make no assumptions regarding conflict resolution are executed in parallel. Therefore, the initial sequential rule-based programs are either executed in parallel without their conflict resolution strategy, which normally results in incorrect behavior, or the programs are transformed in an ad hoc manner to execute on an particular parallel production system model. As a result, these programs do not exhibit the …