Digital Commons Network^™

Formal Derivation Of An Error-Detecting Distributed Data Scheduler Using Changeling, Hanan Lutffiya, Bruce M. Mcmillin, Alan Su

Computer Science Technical Reports

Distributed database applications are a wide use of distributed systems. One of the major advantages of distributed database systems is the potential for achieving high availability in the presence of faults. Faults must be handled so that the system still operates or operates in a degraded mode. This paper focuses on being able to detect component errors which can lead to system failures in the scheduling part of the lock manager portion of the distributed database system by using embedded executable assertions. Changeling provides a systematic approach, based on the mathematical model of program verification, to deriving executable assertions that …

An Analysis Of Product Metrics In Terms Of Qualitative And Formal Metric Properties, Tuliz Dengi, George Zobrist

Computer Science Technical Reports

In recent years, the increased concern for developing reliable, cost-efficient software systems has been accompanied by a higher need to analyze and measure software complexity. Numerous metrics have been proposed to measure software complexity and functionality. Yet, testing the validity of these metrics has been a difficult and long process. As an initial test of metric validity, some researchers have suggested the use of formal metric properties so that metrics without a sound theoretical base are rejected right away. This approach has the additional advantage of allowing a reasonable and fair comparison of software metrics.

In this study, a discussion …

An Object-Oriented Approach To Data Exchange Applications: Development Of A Class Library For The Spatial Data Transfer Standard, Phyllis Altheida, John Prater

Computer Science Technical Reports

The object-orienced paradigm embodies a set of concepts that differentiates it from process-oriented and data-oriented methods. Among che commonly included principles are object, class, encapsulation, inheritance and polymorphism. The synergism of the concepts creates a powerful and new perspective that can be applied to all phases of systems development. Application developers need to try out the object-oriented languages, methodologies and development tools to help define its niche. The problem domain of data transfer standards is used to test the applicability of object-oriented techniques. Data transfer standards have three levels of abstraction: conceptual, logical, and format. The Spatial Data Transfer Standard …

An Animation System For Shift Reduce Parsers, M. S. Mandl, T. J. Sager, D. C. St. Clair

Computer Science Technical Reports

This paper presents the design and implementation of the Parse Display Utility (POU) system. This system introduces a mechanism to augment traditional methods of exploring parsing theory by providing a PRESENTATION scheme which allows a user to view the operation of a shift-reduce parser.

The overall operation of the tool revolves around an LALR (LookAhead LR) parser/parser generator and is managed by a Graphical User-Interface (GUI) developed using Borland's Turbo Vision product. The GUI allows access to a facility which draws derivation trees in Turbo Pascal graphics. This parse tree facility utilizes an algorithm which can easily be ported to …

Effect Of The X² Test On Construction Of Id3 Decision Trees, Mayank Thakore, Daniel C. St. Clair

Computer Science Technical Reports

Inductive machine learning algorithms are knowledge-based learning algorithms which take training instances as input and produce knowledge as output. One popular induction algorithm is Quinlan's ID3 [1986]. This algorithm produces knowledge in the form of a decision tree. Each path in the tree can be interpreted as a rule with the leaves representing rule conclusions. Selected attributes which describe the training instances form the interior nodes of the tree.

The ID3 algorithm is extremely sensitive to noisy training data. In an effort to reduce the effects of noise on tree construction, Quinlan used the X² test to identify noisy …

Multiple-Length Division Revisited: A Tour Of The Minefield, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

Long division of natural numbers plays a crucial role in Cobol arithmetic, cryptography, and primality testing. Only a handful of textbooks discuss the theory and practice of long division, and none of them do it satisfactorily. This tutorial attempts to fill this surprising gap in the literature on computer algorithms. We illustrate the subtleties of long division by examples, define the problem concisely, summarize the theory, and develop a complete Pascal algorithm using a consistent terminology.

Numerical Solution Of Laplace's Equation, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial discusses Laplace's equation for steady state heat flow in a two-dimensional region with fixed temperatures on the boundaries. The equilibrium temperatures are computed for a square grid using successive overrelaxation with parity ordering of the grid elements. The numerical method is illustrated by a Pascal algorithm. We assume that the reader is familiar with elementary calculus.

Parallel Cellular Automata: A Model Program For Computational Science, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

We develop a model program for parallel execution of cellular automata on a multicomputer. The model program is then adapted for simulation of forest fires and numerical solution of Laplace's equation for stationary heat flow. The performance of the parallel program is analyzed and measured on a Computing Surface configured as a matrix of transputers with distributed memory.

All-To-Many Communication Avoiding Node Contention, Sanjay Ranka, Jhy-Chun Wang

Electrical Engineering and Computer Science - Technical Reports

In this paper we present several algorithms for all-too-many personalized communications which avoid node contention.

A Participants' Dss For A Management Game With A Dss Generator, G. K. Yeo, Fiona Fui-Hoon Nah

Research Collection School Of Computing and Information Systems

A decision support system for a management game has been built with emphasis on total model integration, easy database access, and efficient model building by participants themselves. A decision-support-system generator has been used to provide a wide range of modeling capabilities. This article describes its design principles and major features.

Approximation By Interval Bezier Curves, Thomas W. Sederberg, Rida T. Farouki

Faculty Publications

The interval Bezier curve, which, unlike other curve and surface approximation schemes, can transfer a complete description of approximation errors between diverse CAD/CAM systems that impose fundamentally incompatible constraints on their canonical representation schemes, is described. Interval arithmetic, which offers an essentially infallible way to monitor error propagation in numerical algorithms that use floating-point arithmetic is reviewed. Affine maps, the computations of which are key operations in the de Casteljau subdivision and degree-elevation algorithms for Bezier curves, the floating-point error propagation in such computations, approximation by interval polynomials, and approximation by interval Bezier curves are discussed.

Parallel Techniques For Paths, Visibility, And Related Problems (Thesis), Ziyi Danny Chen

Department of Computer Science Technical Reports

No abstract provided.

Formal Generation Of Executable Assertions For Application-Oriented Fault Tolerance, Hanan Lutfiyya, Martina Schollmeyer, Bruce M. Mcmillin

Computer Science Technical Reports

Executable assertions embedded into a distributed computing system can provide run-time assurance by ensuring that the program state, in the actual run-time environment, is consistent with the logical stage specified in the assertions; if not, then an error has occurred and a reliable communication of this diagnostic information is provided to the system such that reconfiguration and recovery can take place. Application- oriented fault tolerance is a method that provides fault detection using executable assertions based on the natural constraints of the application.

This paper focuses on giving application-oriented fault tolerance a theoretical foundation by providing a mathematical model for …

Observing Reusable Password Choices, Eugene H. Spafford

Department of Computer Science Technical Reports

No abstract provided.

Ccis Networking - July 1992, Nova University

CCIS Networking / SCIS Networking magazines

No abstract provided.

Fault Tolerance In Concurrent Systems Through Formal Methods, H. Lutfiyya, B. M. Mcmillin

Computer Science Technical Reports

An important aspect which is often overlooked in the software design cycle is the question of assurance. Many methodologies in the past have attempted to provide assurance efficiently, but have never been sucessful at eliminating explicit time and space redundancy. One approach is the Application-Oriented Fault Tolerance Paradigm, which provides assurance by examining the behavior and propenies of the application and deriving executable assertions for the detection of faults. Previous work has demonstrated the feasibility of the application-oriented fault tolerance paradigm for various applications. However, the executable assertions were guided by the natural constraints of the problem. This work focuses …

Text-Independent Automatic Speaker Identification Using Partitioned Neural Networks, Laszlo Rudasi

Electrical & Computer Engineering Theses & Dissertations

This dissertation introduces a binary partitioned approach to statistical pattern classification which is applied to talker identification using neural networks. In recent years artificial neural networks have been shown to work exceptionally well for small but difficult pattern classification tasks. However, their application to large tasks (i.e., having more than ten to 20 categories) is limited by a dramatic increase in required training time. The time required to train a single network to perform N-way classification is nearly proportional to the exponential of N. In contrast, the binary partitioned approach requires training times on the order of N². …

Neural Modeling And Control Of A Distillation Column, James Edward Steck, K. Krishnamurthy, Bruce M. Mcmillin, Gary G. Leininger

Mechanical and Aerospace Engineering Faculty Research & Creative Works

Control of a nine-stage three-component distillation column is considered. The control objective is achieved using a neural estimator and a neural controller. The neural estimator is trained to represent the chemical process accurately, and the neural controller is trained to give an input to the chemical process which will yield the desired output. Training of both the neural networks is accomplished using a recursive least squares training algorithm implemented on an Intel iPSC/2 multicomputer (hypercube). Simulated results are presented for a numerical example.

Parallel Monte Carlo Trials, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

The best results of Monte Carlo methods are generally obtained by performing the same computation many times with different random numbers. We develop a generic algorithm for parallel execution of Monte Carlo trials on a multicomputer. The generic algorithm has been adapted for simulated annealing and primality testing by simple substitutions of data types and procedures. The performance of the parallel algorithms was measured on a Computing Surface.

Designing Efficient Maximum-Likelihood Soft-Decision Decoding Algorithms For Linear Block Codes Using Algorithm A*, Yunghsiang S. Han, Carlos R.P. Hartmann

Electrical Engineering and Computer Science - Technical Reports

In this report we present a class of efficient maximum-likelihood soft-decision decoding algorithms 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 …

Primality Testing, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial describes the Miller-Rabin method for testing the primality of large integers. The method is illustrated by a Pascal algorithm. The performance of the algorithm was measured on a Computing Surface.

Simulated Annealing, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial describes simulated annealing, an optimization method based on the principles of statistical mechanics. Simulated annealing finds near-optimal solutions to optimization problems that cannot be solved exactly because they are NP-complete. The method is illustrated by a Pascal algorithm for the traveling salesperson problem. The performance of the algorithm was measured on a Computing Surface.

Computer Science Education At Wku, Malcolm Stallings

Mahurin Honors College Capstone Experience/Thesis Projects

No abstract provided.

Ua66/3/2 Computer Science Alumni Newsletter, Vol. 7, Wku Computer Science

WKU Administration Documents

Newsletter created by WKU Computer Science for alumni of the program. This issue includes course offerings, computer lab diagram and an alumni survey.

General Model Theoretic Semantics For Higher-Order Horn Logic Programming, Mino Bai, Howard A. Blair

Electrical Engineering and Computer Science - Technical Reports

We introduce model-theoretic semantics [6] for Higher-Order Horn logic programming language. One advantage of logic programs over conventional non-logic programs has been that the least fixpoint is equal to the least model, therefore it is associated to logical consequence and has a meaningful declarative interpretation. In simple theory of types [9] on which Higher-Order Horn logic programming language is based, domain is dependent on interpretation [10]. To define T p operator for a logic program P, we need a fixed domain without regard to interpretation which is usually taken to be a set of atomic propositions. We build a semantics …

Effects Of Nonsymmetric Release Times On Rate Monotonic Scheduling, R. G. Karl, T. L. Lo, D. C. St. Clair

Computer Science Technical Reports

This paper discusses problems associated with scheduling periodic tasks in a hard, real-time processing or computing environment using a static-priority, preemptive-resume operating system . The scheduling problems associated with a task set containing a single periodic task which has two fixed release periods of unequal length are examined. Some real-world applications may require task release times which are periodic, but whose tasking periods are not symmetric. A scheduling algorithm for task sets with a single nonsymmetric task has been developed for staticpriority, preemptive-resume operating systems. The nonsymmetric scheduling algorithm is based on the rate monotonic scheduling algorithm which assigns higher …

Design Of Backpropagation Neural Network Architectures Using A Decision Tree Classifier, B. M. Van Horn, D. C. St. Clair

Computer Science Technical Reports

The backpropagation neural network algorithm is a popular machine learning methodology. One difficulty with using the algorithm is that the network architecture must be designed before learning can occur. This includes deciding the number of layers, the number of nodes in each layer, and the number of connections. Traditionally this problem is solved by heuristics gained by an expert through experience.

This paper presents an algorithm for using ID3 decision trees to design the network architecture. Previous approaches rely on binary decision trees. The proposed technique utilizes n-ary trees. These trees are easier to understand, are better suited for continuous-valued …

Optimizing Accuracy And Generalization In Numeric Classification Systems, M. D. Walters, D. C. St. Clair

Computer Science Technical Reports

Classifier systems are knowledge-based learning algorithms that take training instances as input and produce a set of rules as output. The classifier systems focused on in this paper represent the knowledge they learn in the form of decision trees, and are built upon Quinlan's [ 1986] inductive algorithm ID3.

The ID3 algorithm suffers from the inability to easily and effectively handle domains with numeric-valued attributes. Numeric attributes are those whose values are taken from a continuous domain or from a domain with a large number of discrete values. A number of approaches have been developed for extending ID3 to handle …

The Identification And Processing Of Don't-Care Attribute Values In Id3 Decision Tree Construction, P. D. Dorr, D. C. St. Clair

Computer Science Technical Reports

ID3 is most successful when used with sets of training and testing data that contain no missing attribute values. Many times, however, real-world domains have attributes with missing values. Sometimes these attribute values may not be needed to classify an instance. Such attribute values are called don't-care attribute values. In other cases, the values are needed but are unavailable. These values are called unknown attribute values. This paper describes the difference between unknown and don't-care attribute values and discusses several ways of identifying don't-care attribute values in ID3. Numerical results are described which validate the practicality of these approaches.

Network Key Management In A Large Distributed Environment, J. J. Stapleton, D. C. St. Clair

Computer Science Technical Reports

The technique of using encryption for protecting information in a network environment involves managing encryption keys within that same network. In large distributed networks the goal of achieving a secure environment requires a secure method of performing network key management. Network security, system security, and application security by means of data encryption rely on encryption keys remaining secret.

Both international and domestic standards organizations such as the International Organization for Standardization (ISO), the American National Standards Institute (ANSI), and the National Institute of Standards and Technology (NIST) address the issues of encryption through various standards. However, these standards discuss methods …