Digital Commons Network^™

An Lr(L) Testing Algorithm, Thomas J. Ssager

Computer Science Technical Reports

A grammar is LR{1} if it can be parsed deterministically from left to right while looking ahead no more than one symbol. Because of the difficulty in generating full LR{l) parsers, many parser generators such as YACC limit themselves to LALR(1} grammars which are a subset of the LR{l) grammars.

Unlike other algorithms in the literature for testing whether a grammar is LR{l), the algorithm presented here uses only the characteristic finite state machine and other structures necessary for creating an LALR{l) parser. Thus, if a parser generator finds that a grammar is not LALR{l), with little additional work the …

The Minlrl Algorithm For Generating Small Lr(L) Parsers, Thomas J. Sager

Computer Science Technical Reports

The MINLRl algorithm for finding minimal deterministic parsers for LR(1) grammars is presented. MINLRl also detects whether a grammar is LR(l) with little more work than building the grammar's LALR(l) parser. MINLRl starts by building the characteristic finite state machine, CFSM, for the input grammar and then checks for LR(l)ness. If the input grammar is LR(l), MINLRl transforms the CFSM into a minimal LR(l) parser by creating extra copies of certain states of the CFSM as necessary. The complexity of the algorithm is O(n³l²v²) where n is the number of states in the parser, …

How To Count Quickly And Accurately: A Unified Analysis Of Probabilistic Counting And Other Related Problems, Peter Kirschenhofer, Helmut Prodinger, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.

A Declarative View Of Inheritance In Logic Programming, M. Bugliesi

Department of Computer Science Technical Reports

No abstract provided.

Unstructured Scheduling In Parallel Pde Sparse Solvers On Distributed Memory Machines, Mo Mu, John R. Rice

Department of Computer Science Technical Reports

No abstract provided.

A Reconstruction Of Context-Dependent Document Processing In Sgml, Allen Brown Jr., T. Wakayama, Howard A. Blair

Electrical Engineering and Computer Science - Technical Reports

SGML achieves a certain degree of context-dependent document processing through attributes and linking. These mechanisms are deficient in several respects. To address these deficiencies we propose augmenting SGML's LINK and ATTLISTconstructs with two new mechanisms, coordination and (rule-based) attribution. The latter can be used to specify the result of context-dependent processing in a uniform fashion while considerably increasing SGML's expressive power. We illustrate this enhanced power by sketching a specification of (the result of) document layout that can be encoded in SGML augmented with coordination and attribution.

Constructively Typed Timed Automata, J. F. Peters Iii

Electrical Engineering and Computer Science - Technical Reports

A new class of communicating automata called typed Timed lnput/Output Automata (tTAi/os) is introduced. A tTAi/o is a predicate automaton used for specifying and reasoning about real-time systems. The typing discipline suggested for predicate automata is in the tradition of Martin-Löf's constructive type theory. A type A is a proposition, which is defined when a prescription for constructing a proof of A is given. A fragment of Girard's linear logic is used in classifying state types. An illustration of the use of tTAi/os in specifying a light-controller is presented. An abstract program is extracted during a proof of an automaton …

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

BITs and PCs Newsletter

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

Quadratic Spline Collocation Methods For Elliptic Partial Differential Equations, Christina C. Christara

Department of Computer Science Technical Reports

No abstract provided.

An Experimental Sequence Examining The Effect Of Task Type, Memory Condition, And Display Presentation Type On Performance Time And Error Rate, Using Columnar Table Versus Vertical Bar Graph Versus Line Graph, Suparna Das

Theses

A total of 126 subjects at various levels of school and a health related manufacturing firm participated in three experiments that compared Tables, Line graphs and Bar graphs forms of data presentation. The experiments were performed each consisting of a training task followed by answering some questions based on the presented material. The experimental series were presented to six groups. Group 1, 3, 5 viewed Line graphs, Tables or Bar graphs respectively while answering the questions while the other three groups answered questions based on memory of either Line graphs, Table or Bar graph presentation.

The independent variables were:

1. Memory …

A Common Application Model For Interfacing With Advanced Program To Program Communication/Vm, Joseph Viviano Jr.

Theses

The Merrill Lynch data processing environment is composed of a conglomeration of applications which reside on various platforms. LAN and minicomputer based applications coexist with those making their home in the mainframe arena. Unfortunately, coexistence does not imply cooperation, data uniformity, data centralization or coordinated application development. Within the Merrill Lynch mainframe arena alone there are two operating systems which reside across several computing complexes, MVS (Multiple Virtual Storage) and VM (Virtual Machine). Critical business applications and data are unique to each of these environments. The problem lies in the need for cooperative processing and sharing of distributed data among …

Complexity Of Network Reliability And Optimal Database Placement Problems, Donald B. Johnson, Larry Raab

Computer Science Technical Reports

A fundamental problem of distributed database design in an existing network where components can fail is finding an optimal location at which to place the database in a centralized system or copies of each data item in a decentralized or replicated system. In this paper it is proved for the first time exactly how hard this placement problem is under the measure of data availability. Specifically, we show that the optimal placement problem for availability is #P- complete, a measure of intractability at least as severe as NP-completeness. Given the anticipated computational difficulty of finding an exact solution, we go …

Electronic Skeletons: Modeling Skeletal Structures With Piecewise Algebraic Surfaces, Chanderjit L. Bajaj

Department of Computer Science Technical Reports

No abstract provided.

Portable 3d Graphics In A Heterogeneous Distributed Environment, Vinod Anupam, Chanderjit L. Bajaj, Malcolm C. Fields, Andrew V. Royappa

Department of Computer Science Technical Reports

No abstract provided.

The Shastra Distributed And Collaborative Geometric Design Environment, Vinod Anupam, Chanderjit L. Bajaj, Andrew V. Royappa

Department of Computer Science Technical Reports

No abstract provided.

Computer Vision, Descriptive Geometry, And Classical Mechanics, Christoph M. Hoffmann

Department of Computer Science Technical Reports

No abstract provided.

Formal Generation Of Executable Assertions For A Fault-Tolerant Parallel Matrix Relaxation, Hanan Lutfiyya, Bruce M. Mcmillin

Computer Science Technical Reports

No abstract provided.

Visual Interaction: A Link Between Perception And Problem Solving, Erika Rogers, Ronald C. Arkin

Computer Science and Software Engineering

The approach taken in this research is to develop a cognitive model of how a human observer extracts information from a visual display and then uses this perceptual information in a decision-making task. Knowledge about this relationship provides information about the occurrence of perceptual events in the course of problem-solving activities, and suggests that perceptual assistance in the form of image enhancements is a useful supplement to the user’s own abilities. This knowledge is then to be embedded in an intelligent computerized assistant which is designed to facilitate and stimulate the human problem-solving process.

How To Compute Offsets Without Self-Intersection, Ching-Shoei Chiang, Christoph M. Hoffmann, Robert E. Lynch

Department of Computer Science Technical Reports

No abstract provided.

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

BITs and PCs Newsletter

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

On The Question ‘Do We Need Identity?’, William C. Purdy

Electrical Engineering and Computer Science - Technical Reports

Sommers posed the question 'Do We Need Identity?' and answered in the negative. According to Sommers, the need for a special identity relation resulted from an arbitrary distinction between concept and object introduced by Frege and retained in modern predicate logic (MPL). This is reflected in the syntactic distinction between predicate and individual constant. Traditional formal logic (TFL) does not respect this distinction and, as a consequence, has no need for a special identity relation. But Sommers' position has not gained general acceptance. On the contrary, it has received considerable criticism. While it is conceded that TFL can express the …

Distributed Memory Compiler Methods For Irregular Problems -- Data Copy Reuse And Runtime Partitioning, Raja Das, Ravi Ponnusamy, Joel Saltz, Dimitri Mavriplis

Electrical Engineering and Computer Science - Technical Reports

This paper outlines two methods which we believe will play an important role in any distributed memory compiler able to handle sparse and unstructured problems. We describe how to link runtime partitioners to distributed memory compilers. In our scheme, programmers can implicitly specify how data and loop iterations are to be distributed between processors. This insulates users from having to deal explicitly with potentially complex algorithms that carry out work and data partitioning. We also describe a viable mechanism for tracking and reusing copies of off-processor data. In many programs, several loops access the same off-processor memory locations. As long …

Resolution Without Unification, William C. Purdy

Electrical Engineering and Computer Science - Technical Reports

Resolution as an inference procedure forms the basis of most automated theorem-proving and reasoning systems. The most costly constituent of the resolution procedure in its conventional form is unification. This paper describes PCS, a first-order language in which resolution-based inference can be conducted without unification. PCS resembles the language of elementary logic with the difference that singular predicates supplant individual constants and functions. The result is a uniformity in the treatment of individual constants, functions and predicates. An especially costly part of unification is the occur check. Since unification is unnecessary for resolution in PCS, the occur check is completely …

Constrained-Latency Storage Access: A Survey Of Application Requirements And Storage System Design Approaches, Richard Staehli, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Applications with Constrained Latency Storage Access (CLSA) are those that have large storage needs and hard constraints on the amount of latency they can tolerate. Such applications present a problem when the storage technology that is cost effective and large enough cannot meet their latency constraints for demand fetching. Examples are found in the developing field of multimedia computing and, to a lesser extent, in real-time database literature. This paper examines the nature of timing constraints at the application-storage interface and defines a classification for both the synchronization constraints of the application and the latency characteristics of the storage system. …

Sidescan Sonar Image Enchancement Using A Decomposition Based On Orthogonal Functions. Applications With Chebyshev Polynomials, Pierre Cervenka, Christian De Moustier

Center for Coastal and Ocean Mapping

A method is presented to remove from sidescan sonar images of the seafloor, artifacts that are clearly unrelated to the backscattering properties of the seafloor. A spectral analysis performed on a ping by ping basis proved to be well suited to the problem. The technique relies on a decomposition using Chebyshev polynomials. This stochastic method does not require a priori knowledge of deterministic parameters. It deals with the low spatial frequency components of the image whose wavelengths are not very small compared to the swath width. Applications to sidescan sonar images obtained with the SeaMARC LI system are presented.

A Practical Hierarchical Model Of Parallel Computation Ll: Binary Tree And Fft Algorithms, Todd Heywood, Sanjay Ranka

Electrical Engineering and Computer Science - Technical Reports

A companion paper has introduced the Hierarchical PRAM (H-PRAM) model of parallel computation, which achieves a good balance between simplicity of usage and reflectivity of realistic parallel computers. In this paper, we demonstrate the usage of the model by designing and analyzing various algorithms for computing the complete binary tree, and the FFT/butterfly graph. By concentrating on two problems, we are able to demonstrate the results of different combinations of organizational strategies and different types of sub-models of the H-PRAM. The philosophy in algorithm design is to maximize the number of processors P that are efficiently usable with respect to …

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 …

Approaches To High Speed Networks, Frank Charles Paterra

Computer Science Theses & Dissertations

This work investigates possible methods by which existing potentially available communication bandwidth can be used by communication intensive applications. Presently fiber optic media are available that can provide multiple gigabits of throughput. Unfortunately, because of the computation overhead required to insure that data are reliably transmitted this capacity has not been tapped.

A survey of work toward enabling the use of the potential bandwidth is presented. The parallel paradigm is identified as a strong candidate for providing significant increases in system usable bandwidth. Performing communication processing in parallel, however, presents the developer with several implementation options. These options are considered …

Domain Limitations And Interface Requirements For Expert Developed Knowledge Based Systems, Bernard Lee Lewis

Engineering Management & Systems Engineering Theses & Dissertations

The expanded use of graphical, case-based and object oriented techniques in expert systems creation has made it more practical for domain experts to develop their own applications. This thesis focuses on the elements necessary in an expert/developer interface and looks at various forms and techniques that exemplify such an approach. The spreadsheet metaphor is used for an interface or managed set of interfaces that a domain expert can use in building his own expert system or prototype. criteria are established for such interfaces and recent commercial offerings that make expert-created knowledge-bases more practical are reviewed for techniques that qualify. Approaches …

Computer Simulation Techniques To Assess Bias And Precision In The Roving Creel Survey Estimator, David L. Wade

Biological Sciences Theses & Dissertations

Fisheries scientists use roving creel survey methods to estimate total catch and total effort of recreational fisheries. Bias in the roving creel estimators had been known to the scientific community, but it had not been quantified. I developed a roving-creel-survey computer simulation model to investigate the bias and precision of roving creel estimators, and estimated parameters for the model based on field observations from the blue crab (Callinectes sapidus) fishery of the Chesapeake Bay. The computer model was used to identify bias in roving-creel effort and catch estimators and to demonstrate survey methods that will reduce this bias. …