Computer Science Technical Reports
Permanent URI for this collection
The Department of Computer Science collection of technical
reports began in 1973. Please use the subject headings listed below for all submissions.
Subject Headings:
- Algorithms
- Big Data
- Bioinformatics
- Computational Biology
- Computational Science and Engineering
- Computer Graphics/Animation
- Computer Science Education
- Computer Systems
- Cyberarts
- Cybersecurity
- Data and Text Mining
- Digital Education
- Digital Libraries
- Discrete Event Simulation
- High Performance Computing
- Human Computer Interaction
- Information Retrieval
- Machine Learning
- Mathematical Programming
- Mathematical Software
- Modeling and Simulation
- Networking
- Numerical Analysis
- Parallel and Distributed Computing
- Problem Solving Environments
- Software Engineering
- Theoretical Computer Science
- Virtual/Augmented Reality
- Visualization
Browse
Browsing Computer Science Technical Reports by Issue Date
Now showing 1 - 20 of 1036
Results Per Page
Sort Options
- A Complete Horizontal MicrolanguageWesselkamper, Thomas C.; Nixon, Eric (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)This paper defines a data space whose points are trees with leaves which are [name,value] pairs. Over this space a substitution operator S (meaning informally "in x for y put z") is formally defined. Taken together with several auxiliary operators, S is shown to be sufficient to define a large class of high-level languages since S is known to be functionally complete for finite-valued spaces, a functionally complete language is exhibited.
- Microprogrammable Cellular AutomataMuzio, Jon C.; Wesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)This paper reports research into cellular automata with two binary inputs, two binary outputs, and an octal control variable. A set of control variables is chosen and it is shown that any function of three variables can be realized by a 2 x 2 array of cells, any function of four variables by a 2 x 6 array of cells. A construction based on the Shannon Decomposition Theorem is given for the realization of functions of more than four variables. The existence of a more efficient construction is conjectured. A definition of the circuit defining the cell is given as well as an implementation using NAND gates. A practical configuration of the cells is suggested and fault correction is discussed.
- Functionally Complete MachinesWesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)This paper defines a functionally complete machine as a machine which is capable of evaluating every two place function over its data space. Necessary conditions on memory size for completeness are developed. These conditions are applied to System/360 as modelled by the space of bytes, the space of halfwords, and the space of words. Sufficiently large (> 64K bytes) models of System/360 are shown to be complete for the space of bytes. No models of System/360 are complete for the spaces of halfwords or words. The inequalities developed and known examples of universal decision elements suggest structures for complete machines.
- Fol: A Language for Implementing File Organizations for Information Storage And Retrieval SystemsClaybrook, Billy G. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)The language FOL is described. FOL facilitates the implementation of file organizations for IS & R systems. FOL is implemented in a list processing language LPL. Files in FOL are interepreted as a list of records, where each record is equivalent to a node structure. A description of LPL is also included.
- Generalized Structured ProgrammingMartin, Johannes J. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)In an effort to eliminate some inconveniences connected with Dijkstra's method of Structured Programming, a generalized set of basic flow graphs for structuring programs is suggested. These structures generate the set of all flow graphs that can be fully decomposed by Allen and Cocke's method of interval reduction. It will be shown that programs Composed of the proposed basic structures have most, if not all, of the Positive characteristics claimed for programs written with the classic rules of Structured Programming. Further, by extending Wirth's programming language PASCAL a set of new control constructs has been suggested that support the proposed set of flow structures.
- Dynamic Quantum Allocation and Swap-Time Variability in Time-Sharing Operating SystemsBhat, U. Narayan; Nance, Richard E. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)No abstract available.
- Lpl: A Generalized List Processing LanguageClaybrook, Billy G. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)The paper describes LFL, a generalized list processing language. LFL allows the user to define multiple cell structures and cell sizes at runtime, thereby allowing nonhomogeneous list structures. The paper examines the problems associated with list tracing in systems allowing multiple cell-types. Complex list tracing during garbage collection in LFL is avoided: (1) by creating a doubly-linked super list of all allocated cells and (2) by using a reference count scheme. No marking phase is required for garbage collection. The problem of developing insertion and deletion procedures for lists with cells having multiple types of pointer structures is discussed and LFL solutions are given. LPL statements can handle singly-linked, doubly-linked, left-right-linked, and some multi-linked pointer structures automatically. The design philosophy and the data organization for LPL are discussed in detail. Examples of the definition of cell structures are given, and all of the LPL list manipulation and creation statements arc examined and discussed.
- A Topological Model of the Data Space for a Block Structured LanguageWesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)A space X is defined, the points of which are trees which possess a unique name property. A topology is defined for X based upon partial order. The topology is shown to be reasonably natural relative to the rationals. The topological space is shown to be neither Hausdorff nor T_1. The implications of this for program convergence are discussed with examples.
- The Dynamic Creation And Modification of Heuristics in a Learning ProgramClaybrook, Billy G.; Nance, Richard E. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1973)POLY FACT is a learning program that attempts to factor multivariable polynomials. The program has been successful in factoring polynomials (in simplified form) with a maximum of 84 terms, each term consisting of as many as five variables and a maximum degree of 67. The complexity of this learning task placed unusual requirements on the representation of heuristics. By using the first-order predicate calculus notation, we enable the creation and modification of heuristics dynamically during program execution. Constraints on the creation process are implemented in a series of tables by which one can alter the flexibility given to the program. Execution of heuristics begins with a translation of the predicate calculus representation to a reverse Polish string, followed by the interpretive evaluation of the Polish string. A general procedure for developing and implementing the predicate calculus representation is suggested.
- The Relationship Between the Multiplicative And Mixed Generators Modulo 2^bOverstreet, Claude Jr. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)MacLaren and Marsaglia [4] comment that their test results suggest that the multiplicative generator performs better than the mixed generator. We attempt to answer the above question by showing that for any sequence of real values in (0,1) produced by the multiplicative generator modulo 2^b a corresponding mixed generator exists which, for practical purposes, produces the same sequence of real values.
- Analysis of an Enumeration Algorithm for Unordered K-partitions of NKang, Andy N. C.; Kang, C. K. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)In many combinatorial problems, the need to compute the number of unrestricted partitions of n or to enumerate over the set of unrestricted partitions of n occurs frequently. Let two positive integers k and n be given, the set of unordered k-tup1es (a1,a2,..., ak) of positive integers such that a1+a2+...+ak=n is called the unordered k-partitions of n. In this paper, an algorithm to enumerate the set is presented and analyzed. The running time of the algorithm is shown to be linearly proportional to the number of elements in the set. The number of unordered k-partitions of n, f_k(n), is given in a recurrence relation as a byproduct. With these results, to enumerate the unrestricted partitions of n, we need only to enumerate successfully the unordered 1- partition of n, 2-partitions of n, ... , up to n-partitions of n.
- Implementation of Fortran Random Number Generators on Computers with One's Complement ArithmeticNance, Richard E.; Overstreet, Claude Jr. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)No abstract available.
- On Making Bairstow's Method WorkAult, David A. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)No abstract available.
- A Total Algorithm for Polynomial Roots Based Upon Bairstow's MethodAult, David A. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)This program uses Bairstow's method to find the real and complex roots of a polynomial with real coefficients. There are several reasons for developing a routine based upon Bairstow's method. It is sometimes the case that all of the roots of a polynomial with real coefficients are desired. Bairstow's method provitles an iterative process for finding both the real and complex roots using only real arithmetic. Further, since it is based on Newton's method for a system of two nonlinear equations in two unknowns, it has the rapid convergence property of Newton's method for systems of equations. The major drawback of this method is that it sometimes fails to converge [11, p. 110]. This is because it is difficult to find an initial starting guess which satisfies the strict conditions necessary to assure convergence. When these conditions are not satisfied, the sequence of approximations may jump away from the desired roots or may iterate away from the roots indefinitely.
- Principle of Optimal Page Replacement and the LRU Stack ModelLam, Felix L. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)Program reference strings generated by the LRU stack model are considered, and expressions for the expected times to next reference for all pages occupying different LRU stack positions are derived. Using these expressions, necessary and sufficient conditions as well as sufficient conditions on the distance distribution are obtained which guarantee implementation by the LRU replacement algorithm of the "informal principle of optimality" for page replacements. The sufficient conditions are found to be the same as those under which the LRU replacement algorithm is shown to be optimal. Relaxed conditions are also obtained for special cases where the number of page frames is fixed.
- An Artificial Intelligence Approach to the Symbolic Factorization of Multivariable PolynomialsClaybrook, Billy G. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)A new heuristic factorization scheme that uses learning to improve the efficiency of determining the symbolic factorization of multivariable polynomials with integer coefficients and an arbitrary number of variables and terms is described. The factorization scheme makes extensive use of Artificial Intelligence techniques, e.g. model-building, learning, and automatic classification in an attempt to reduce the amount of searching for the irreducible factors of a polynomial. The approach taken to polynomial factorization is quite different from previous attempts because: (1) it is distinct from numerial techniques, (2) possibilities for terms in a factor are generated from the terms in the polynomial, and (3) a reclassification technique is used to allow the application of different sets of heuristics to a polynomial during factorization attempts on it. Tables are presented that demonstrate the importance of learning to the efficiency of operation of the scheme. Factorizat5.on times of polynomials factored by both the scheme described in this paper and Wang's implementation of Berlekamp's algorithm are given and compared and an analysis of variance experiment provides an indication of the significant sources of variation influencing the factorization time.
- The Role of Automatic Digitizers in DemographyWilliams, Charles M. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)The incorporation of facilities for automatically digitizing maps and drawings can considerably enhance the power of the computer in demographical research. A hardware-software process is described which can rapidly, economically, and automatically digitize hard-copy maps and drawings. The resultant computer data structures are a faithful and accurate representation of both the original geometry and topology and may thus serve as a direct source of data for analysis or display. The potential uses for this system appears to be large for, though maps and drawings are of fundamental importance to demographers, their transduction into computers has historically been stymied by the problems associated with tedious, inaccurate, and incomplete manual methods.
- A Computer Implementation of the Transformations of Formulas into Prenex Normal FormProvenza, Clinton E. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)The purpose of this paper is to explain a computerized process whereby any well-formed formula (wff) of first order predicate calculus can be moved to its prenex normal form (PNF). The main features of the program demonstrate some of the interesting capabilities of the WATFIV compiler in utilizing Markov Algorithms.
- Root-heavy Directory Tree on Direct Access Storage DevicesShen, Stewart N.T. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)No abstract available.
- GLM Versus Continuous Approximation for Convex Integer ProgramsGreenberg, Harvey J. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)GLM is compared to continuous approximation for convex, integer programs. After noting the stronger bound provided by GLM, Lagrangian duality and a gap closing heuristic is used to demonstrate how GLM may provide a better feasible policy as well.