Digital Commons Network^™

Closed-Network Duals Of Multiques With Application To Token-Passing Systems, Vernon J. Rego, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.

A New Approach To The Dynamic Maintenance Of Maximal Points In A Plane, Greg N. Frederickson, Susan Rodger

Department of Computer Science Technical Reports

No abstract provided.

Meta-Level Programming: A Compiled Approach, Hamid Bacha

Electrical Engineering and Computer Science - Technical Reports

There has been some intense research lately focused on the area of meta-level inference systems. In logic programming, the limitations of Prolog are widely recognized and a meta-level approach has been suggested. Unfortunately, only meta-interpreters have been considered so far. Moreover, these meta-interpreters are often themselves written on top of a Prolog interpreter. These cascaded layers of interpreters result in an enormous slow down, rendering the resulting system practically useless for all but a small number of toy applications. This paper will report on the implementation of a fast incremental metaProlog compiler. In the process, it will explore some of …

A Dynamic Caching Algorithm Based On C. C. Chang's Ordered Minimal Perfect Hashing Scheme, Thomas J. Sager

Computer Science Technical Reports

No abstract provided.

A Routing Algorithm For Three Stage Rearrangeable Clos Networks, Ralph W. Wilkerson

Computer Science Faculty Research & Creative Works

No abstract provided.

The Performance Of Numerical Methods For Elliptic Problems With Mixed Boundary Conditions, Wayne R. Dyksen, Calvin J. Ribbens, John R. Rice

Department of Computer Science Technical Reports

No abstract provided.

An Experimental Implementation Of The Tilde Naming System, Douglas E. Comer, Ralph E. Droms, Thomas P. Murtagh

Department of Computer Science Technical Reports

No abstract provided.

A Logic Programming Model Of The Game Of Sprouts, Ralph M. Butler, Selden Y. Trimble, Ralph W. Wilkerson

Computer Science Faculty Research & Creative Works

The Game of Sprouts Has Intrigued Mathematicians for Nearly Twenty Years. This Paper Describes a Representation Scheme Which Simplifies Much of the Geometry of the Game. using This Representation, We Develop a Prolog Program Which Will Play Sprouts. It is Hoped that the Program Will Prove to Be a Useful Research Tool in Finding the Key to a Winning Strategy for Sprouts and that the Representation Will Serve as a Useful Model for Studying Planar Graphs.

A Logic Programming Model Of The Game Of Sprouts, Ralph M. Butler, Selden Y. Trimble, Ralph W. Wilkerson

Computer Science Faculty Research & Creative Works

The Game of Sprouts Has Intrigued Mathematicians for Nearly Twenty Years. This Paper Describes a Representation Scheme Which Simplifies Much of the Geometry of the Game. using This Representation, We Develop a Prolog Program Which Will Play Sprouts. It is Hoped that the Program Will Prove to Be a Useful Research Tool in Finding the Key to a Winning Strategy for Sprouts and that the Representation Will Serve as a Useful Model for Studying Planar Graphs. © 1987, ACM. All Rights Reserved.

Lily-A Generator For Compiler Frontends, Thomas J. Sager

Computer Science Technical Reports

In this paper, LILY, a generator for compiler frontends is described. LILY uses a generator of minimal perfect hash functions, MPHF , to create small fast compilers.

A Dynamic Caching Algorithm Based On C. C. Chang's Ordered Minimal Perfect Hashing Scheme, Thomas J. Sager

Computer Science Technical Reports

An algorithm for storage and retrieval in a small dynamic cache is presented. This algorithm is based on C.C. Chang’s ordered minimal perfect hashing scheme. Our algorithm has the property that it divides the set of objects that could occupy the cache into an arbitrary number of equivalence classes. The only restriction on which objects can occupy the cache are that no two objects in the same equivalence class can be in the cache at the same time. Retrieval from the cache is performed in constant time. Update of the cache is performed in logarithmic time.

An Attribute-Grammar Implementation Of Government-Binding Theory, Nelson Correa

Electrical Engineering and Computer Science - All Scholarship

The syntactic analysis of languages with respect to Government binding (GB) grammar is a problem that has received relatively little attention until recently. This paper describes an attribute grammar specification of the Government binding theory. The paper focuses on the description of the attribution rules responsible for determining antecedent trace relations in phrase-structure trees, and on some theoretical implications of those rules for the GB model. The specification relies on a transformation-le variant of Government "binding theory, briefly discussed by Chomsky (1981), in which the rule move-a is replaced by an interpretive rule. Here the interpretive rule is specified by …

Sorting And Selecting In Rounds, Nicholas Pippenger

All HMC Faculty Publications and Research

We present upper bounds for sorting and selecting the median in a fixed number of rounds. These bounds match the known lower bounds to within logarithmic factors. They also have the merit of being “explicit modulo expansion”; that is, probabilistic arguments are used only to obtain expanding graphs, and when explicit constructions for such graphs are found, explicit algorithms for sorting and selecting will follow. Using the best currently available explicit constructions for expanding graphs, we present the best currently known explicit algorithms for sorting and selecting in rounds.

The Complexity Of Computations By Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

We survey the current state of knowledge concerning the computation of Boolean functions by networks, with particular emphasis on the addition and multiplication of binary numbers.

Proof And Intuition, Michael Detlefsen

ACMS Journal 2004

This paper aims to give a clear exposition of two critiques of logicism. The intuitionist, Brouwer, is best known for rejecting the law of the excluded middle (his "special critique.") The paper argues that Brouwer's "general critique" is deeper and more extensive than this. That is, Brouwer is arguing that mathematical knowledge requires a kind of direct mathematical experience, analogous to sensory experience and this cannot be attained simply by linguistic operations independently of experience. It also discusses Poincare's critiques - that there is a huge difference between genuine mathematical insight and an ability to logically manipulate mathematical truths and …

Nova University Doctor Of Education In Computer Education [1987], Nova University

Abraham S. Fischler College of Education and School of Criminal Justice College Archive

No abstract provided.

The Gradient Model Load Balancing Method, Frank C. H. Lin, Robert M. Keller

All HMC Faculty Publications and Research

A dynamic load balancing method is proposed for a class of large-diameter multiprocessor systems. The method is based on the "gradient model," which entails transferring backlogged tasks to nearby idle processors according to a pressure gradient indirectly established by requests from idle processors. The algorithm is fully distributed and asynchronous. Global balance is achieved by successive refinements of many localized balances. The gradient model is formulated so as to be independent of system topology.

Belief Maintenance Systems: Initial Prototype Specification, Roseanne M. Fulcomer, William E. Ball, John P. Tadlock

All Computer Science and Engineering Research

A fundamental need in future information systems is an effective method of accurately representing and monitoring dynamic, real-world situations inside a computer. Information is represented using an Extended Open World Assumption (EOWA), in which the data are explicitly true or false. Reasoning within the EOWA is done through the use of a dynamic dependency net which only represents those beliefs and justifications that are both currently valid and in current use. In this paper, we present definitions and uses of the EOWA and dynamic dependency net in our current research of developing a database with which we can use deductive …

The Implementation Of A Compiler Targeted To A Multiprocessor Environment, R. Dwight Schettler

Masters Theses

"This research is an application of the techniques which have been developed for the detection and exploitation of implicit parallelism. A system has been developed based on Intel 86/12A single board computers utilizing dual-port RAM for communication. The compiler system accepts the source code of a simple block structured language and generates parallel programs to be executed on the Multibus system. The techniques used for detection of parallelism are stressed"--Abstract, page ii.

Medial Axis Transform Using Ridge Following, Richard Mark Volkmann

Masters Theses

"The intent of this investigation has been to find a robust algorithm for generation of the medial axis transform (MAT). The MAT is an invertible, object centered, shape representation defined as the collection of the centers of disks contained in the shape but not in any other such disk. Its uses include feature extraction, shape smoothing, and data compression. MAT generating algorithms include brushfire, Voronoi diagrams, and ridge following. An improved implementation of the ridge following algorithm is given. Orders of the MAT generating algorithms are compared. The effects of the number of edges in the polygonal approximation, shape area, …

Strategic Planning For A Special Library, Donald A. Guerriero

CCAC Theses and Dissertations

STRATEGIC PLANNING FOR A SPECIAL LIBRARY

The Technical and Management Information Center of the U.S. Defense Communications Agency is a special library providing worldwide library and information services in the subject fields of communications, electronics, command and control, and computer sciences. A project was designed with the objective of developing a strategic plan for this library. Long-range and strategic planning methods commonly used in business organizations were used. An extensive review of the literature on strategic planning was done to determine the best methods available for use in a special library environment. The methods used to develop the strategic plan …

The Computer As A Collection Management Tool, Suzanne B. Mclaren, Hugh H. Genoways, Duane A. Schlitter

University of Nebraska State Museum: Mammalogy Papers

Since the mid-1960s, discussion of computer use for information retrieval in museum collections has usually focused on research potential. Much attention has been given to the idea of networking and the ability to access data across great distances. However, the potential for collection management usage has also proven to be a legitimate rationale for computerization. Numerous aspects of collection management are discussed for which the computer may be employed. Topics include creating cross-reference files, updating taxonomic and geographic information, pinpointing mismatched specimens, locating lost and uncataloged material, controlling loan procedures, producing accession files for insurance purposes, curating all or part …

Mpj: A Proposed Java Message Passing Api And Environment For High Performance Computing, Mark Baker, Bryan Carpenter

Northeast Parallel Architecture Center

In this paper we sketch out a proposed reference implementation for message passing in Java (MPJ), an MPI-like API from the Message-Passing Working Group of the Java Grande Forum [1,2]. The proposal relies heavily on RMI and Jini for finding computational resources, creating slave processes, and handling failures. User-level communication is implemented efficiently directly on top of Java sockets.

Training For The Airland Battle With Modeling And Simulation On The Microcomputer, David Dean Holmes

Masters Theses

"This paper describes a methodology for modifying a combat training simulation model to include a comprehensive data structure and computer software, to allow the model to be implemented on a microcomputer. It begins by developing a topology for combat simulation models and proceeds to define a data structure suitable for describing military units and facilitating the varied aspects of the simulation. An eclectic approach to the development of the model and the implementing software is followed throughout. Appropriate aspects of a number of models are incorporated into a single model suitable for training military commanders and their staffs. PASCAL, a …

Multilist And Inverted File System Performance Measurements, Ashok Chandramouli

Masters Theses

"This study evaluates the multilist and inverted file systems. It describes the structure of the two file system and then proceeds to investigate the performance. The performance is based on quantitative estimates of space requirements for file system, time to retrieve records, time to insert a record, time to delete a record, time to update a record and time to exhaustively read and reorganize the file system. The study then investigates specific situations in which one file system seems to perform better than the other"--Abstract, page ii.

A Proposed C Language Binding For The Graphical Kernel System-3d, Mark Gerard Bolten

Masters Theses

"This thesis introduces a proposed C language binding definition for the International Standards Organization's draft international standard of the Graphical Kernel System-3D. This work augments the earlier C language binding of the two dimensional version of the Graphical Kernel System commonly known as GKS. The proposed function interface will provide a basis for, if not a final, C language binding for the three dimensional version of the Graphical Kernel System"--Abstract, page ii.

A.R.M.S., Arbitrary Robot Modeling System, William Richard Gerlt

Masters Theses

“This paper deals with the mathematical modeling of robot arms. Modeling robot arms includes finding a suitable way to describe a robot, turning the description into a mathematical system, and using the system to find a set of equations which can be used to control the robot.

One of the problems associated with robot modeling is that it involves a great deal of mathematics. When the process is done by hand, the large volume of mathematics makes the process very time consuming and prone to errors. These problems are part of the motivation for automating the modeling of robots.

ARMS …

Lily-A Generator For Compiler Frontends, Thomas J. Sager

Computer Science Technical Reports

No abstract provided.

The Slicing Extent Technique For Fast Ray Tracing, Sudhanshu Kumar Semwal

Retrospective Theses and Dissertations

A new technique for image generation using ray tracing is introduced. The “Slicing Extent Technique” (SET) partitions object space with slicing planes perpendicular to all three axes. Planes are divided into two dimensional rectangular cells, which contain pointers to nearby objects. Cell size and the space between slices varies, and is determined by the objects’ locations and orientations. Unlike oct-tree and other space-partitioning methods, SET is not primarily concerned with dividing space into mutually exclusive volume elements (‘voxels’) and identifying objects within each voxel. Instead, SET is based on analysis of projections of objects onto slicing planes. In comparison to …

Design And Performance Analysis Of A Relational Replicated Database Systems, Jon Gregory Hanson

Retrospective Theses and Dissertations

The hardware organization and software structure of a new database system are presented. This system, the relational replicated database system (RRDS), is based on a set of replicated processors operating on a partitioned database. Performance improvements and capacity growth can be obtained by adding more processors to the configuration. Based on designing goals a set of hardware and software design questions were developed. The system then evolved according to a five-phase process, based on simulation and analysis, which addressed and resolved the design questions. Strategies and algorithms were developed for data access, data placement, and directory management for the hardware …