Physical Sciences and Mathematics Commons^™

A Self-Organizing Binary Decision Tree For Incrementally Defined Rule-Based Systems, Douglas M. Campbell, Tony R. Martinez

Faculty Publications

This paper presents an adaptive self-organizing concurrent system (ASOCS) model for massively parallel processing of incrementally defined rule systems in such areas as adaptive logic, robotics, logical inference, and dynamic control. An ASOCS is an adaptive network composed of many simple computing elements operating asynchronously and in parallel. This paper focuses on adaptive algorithm 3 (AA3) and details its architecture and learning algorithm. It has advantages over previous ASOCS models in simplicity, implementability, and cost. An ASOCS can operate in either a data processing mode or a learning mode. During the data processing mode, an ASOCS acts as a parallel …

Work-Preserving Real-Time Emulation Of Meshes On Butterfly Networks, Alf-Christian Achilles

Theses

The emulation of a guest network G on a host network H is work-preserving and real-time if the inefficiency, that is the ratio W_G/W_H of the amounts of work done in both networks, and the slowdown of the emulation are O(1).

In this thesis we show that an infinite number of meshes can be emulated on a butterfly in a work-preserving real-time manner, despite the fact that any emulation of an s x s-node mesh in a butterfly with load 1 has a dilation of Ω(logs).

The recursive embedding of a mesh in a butterfly presented by …

The Vaidak Medical Imaging And Model Reconstruction Toolkit, Brian Bailey, Chanderjit Bajaj, Malcolm C. Fields

Department of Computer Science Technical Reports

No abstract provided.

The Ganith Algebraic Geometry Toolkit V 1.0, Chanderjit Bajaj, Andrew V. Royappa

Department of Computer Science Technical Reports

No abstract provided.

Suffix Trees Revisited: (Un)Expected Asymptotic Behaviors, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.

Xs: A Hardware Independent Graphics And Windows Library, Vinod Anupam, Chanderjit L. Bajaj, Andrew Burnett, Malcolm C. Fields, Andrew V. Royappa

Department of Computer Science Technical Reports

No abstract provided.

Computer Viruses And Ethics, Eugene H. Spafford

Department of Computer Science Technical Reports

No abstract provided.

C1 Smoothing Of Polyhedra With Implicit Surface Patches, Chanderjit L. Bajaj, Insung Ihm

Department of Computer Science Technical Reports

No abstract provided.

Using Algebraic Geometry For Multivariate Hermite Interpolation, Chanderjit L. Bajaj

Department of Computer Science Technical Reports

No abstract provided.

On A Matrix Identity Connecting Iteration Operators Associated With A P-Cyclic Matrix, Apostolos Hadjidimos, Dimitrios Noutsoss

Department of Computer Science Technical Reports

No abstract provided.

On Surface Design With Implicit Algebraic Surfaces (Ph.D. Thesis), Insung Ihm

Department of Computer Science Technical Reports

No abstract provided.

Decompositions Of Polyhedra In Three Dimensions (Ph.D. Thesis), Tamal Krishna Dey

Department of Computer Science Technical Reports

No abstract provided.

Explicit Clock Temporal Logic In Timing Constraints For Real-Time Systems, S. Ramanna, J. F. Peters Iii

Electrical Engineering and Computer Science - Technical Reports

A form of explicit clock temporal logic (called TLrt) useful in specifying timing constraints on controller actions, a real-time database (rtdb) items, and constraints in a real-time constraint base (rtcb), is presented. Timing as well as other forms of constraints are stored in the rtcb. A knowledge-based approach to ensure the integrity of information in an rtdb is given. The rtcb is realized as a logic program called Constrainer, which is a historyless integrity checker for a real-time database. The consistency and integrity issues for an rtcb and rtdb are investigated. The formal bases for a temporally complete rtdb and …

An Improved Algorithm For Neural Network Classification Of Imbalanced Training Sets, Rangachari Anand, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

In this paper, we analyze the reason for the slow rate of convergence of net output error when using the backpropagation algorithm to train neural networks for a two-class problems in which the numbers of exemplars for the two classes differ greatly. This occurs because the negative gradient vector computed by backpropagation for an imbalanced training set does not point initially in a downhill direction for the class with the smaller number of exemplars. Consequently, in the initial iteration, the net error for the exemplars in this class increases significantly. The subsequent rate of convergence of the net error is …

Semi-Distributed Load Balancing For Massively Parallel Multicomputer Systems, Ishfaq Ahmad, Arif Ghafoor

Electrical Engineering and Computer Science - Technical Reports

This paper presents a semi-distributed approach, for load balancing in large parallel and distributed systems, which is different from the conventional centralized and fully distributed approaches. The proposed strategy uses a two-level hierarchical control by partitioning the interconnection structure of a distributed or multiprocessor system into independent symmetric regions (spheres) centered at some control points. The central points, called schedulers, optimally schedule tasks within their spheres and maintain state information with low overhead. We consider interconnection structures belonging to a number of families of distance transitive graphs for evaluation, and using their algebraic characteristics, show that identification of spheres and …

Collision Detection And Analysis In A Physically Based Simulation, William J. Bouma, George Vanĕček

Department of Computer Science Technical Reports

No abstract provided.

Selective Inheritance And Overriding In Statically-Typed Object-Oriented Languages, Ryan Stansifer, Dan Wetklow

Department of Computer Science Technical Reports

No abstract provided.

Type Reconstruction For Coercion Polymorphism (Technical Summary), Ryan Stansifer, Dan Wetklow

Department of Computer Science Technical Reports

No abstract provided.

Representation Requirements For Supporting Decision-Model Formulation, Tze-Yun Leong

Research Collection School Of Computing and Information Systems

This paper outlines a methodology for analyzing the representational support for knowledge-based decision-modeling in a broad domain. A relevant set of inference patterns and knowledge types are identified. By comparing the analysis results to existing representations, some insights are gained into a design approach for integrating categorical and uncertain knowledge in a context sensitive manner.

Handling Constraints In Genetic Algorithms, Cezary Janikow, Zbigniew Michalewicz

Cezary Janikow

Multidimensional Digital Searching And Some New Parameters In Tries, Peter Kirschenhofer, Helmut Prodinger, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.

Parallel Algorithms For Graph Problems, Panagiotis T. Metaxas

Panagiotis T Metaxas

PhD Thesis about computing connected components in parallel.

Nonlinear System Identification Using Recurrent Networks, Hyungkeun Lee, Y. Park, Kishan Mehrotra, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

This paper presents empirical results on the application of neural networks to system identification and inverse system identification. Recurrent and Feedforward network models are used to build an emulator of a simple nonlinear gantry crane system, and for the inverse dynamics of the system. Recurrent networks were observed to perform slightly better than feedforward networks for these problems.

A Generic Multiplication Pipeline, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This paper illustrates the benefits of developing generic algorithms for parallel programming paradigms which can be adapted to different applications. We consider a combinatorial problem called tuple multiplication. This paradigm includes matrix multiplication and the all-pairs shortest paths problem as special cases. We develop a generic pipeline for tuple multiplication. From the generic algorithm we derive pipelines for matrix multiplication and shortest paths computation by making substitutions of data types and functions. The performance of the matrix multiplication pipeline is analyzed and measured on a Computing Surface.

Constructing Real-Time Systems From Temporal I/O Automata, J. F. Peters Iii, S. Ramanna

Electrical Engineering and Computer Science - Technical Reports

A new class of communicating automata called Temporal Input/Output Automata (TAi/os) is introduced. A TAi/o is a predicate automaton used to specify real-time systems. The specification provided by a TAi/o includes state predicates with proof expressions and abstract program syntax as attributes. An abstract program is extracted during a constructive proof of the specification using the proof expressions. A TAi/o specification also includes hard, real-time constraints on program behavior. The predictability of deterministic, temporally complete TAi/o is investigated. The formulation of real-time system transductions and transduction rules for TAi/os in explicit clock temporal logic is given. An illustration of the …

The Complexity Of Local Stratification, Peter Cholak, Howard A. Blair

Electrical Engineering and Computer Science - Technical Reports

The class of locally stratified logic programs is shown to be Π11-complete by the construction of a reducibility of the class of infinitely branching nondeterministic finite register machines.nondeterministic finite register machines.

Fault-Tolerant Load Management For Real-Time Distributed Computer Systems, Arif Ghafoor, Ishfaq Ahmad

Electrical Engineering and Computer Science - Technical Reports

This paper presents a fault-tolerant scheme applicable to any decentralized load balancing algorithms used in soft real-time distributed systems. Using the theory of distance-transitive graphs for representing topologies of these systems, the proposed strategy partitions these systems into independent symmetric regions (spheres) centered at some control points. These central points, called fault-control points, provide a two-level task redundancy and efficiently re-distribute the load of failed nodes within their spheres. Using the algebraic characteristics of these topologies, it is shown that the identification of spheres and fault-control points is, in general, is an NP-complete problem. An efficient solution for this problem …

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

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 …