Browsing by Author "Wesselkamper, Thomas C."

Now showing 1 - 16 of 16
  • Thumbnail Image
    The Algebraic Representation of Partial Functions
    Wesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1978)
    The paper presents a generalization of the theorem which states that any (everywhere defined) function from a finite field GF(p^n) into itself may be represented at a polynomial over GF(p^n). The generalization is to partial functions over GF(p^n) and exhibits representations of a partial function f by the sum of a polynomial and a sum of terms of the form a/(x-b)i, where b is one of the points at which f is undefined. Three such representation theorems are given. The second is the analog of the Mittag-Leffler Theorem of the theory of functions of a single complex variable. The main result of the paper is that the sum of the degree of the polynomial part of the representation and the degrees of the principal parts of the representation need be no more than max(|A|, |B|) where A is the set upon which the function is defined and B is the set upon which the function is undefined.
  • Thumbnail Image
    A Complete Horizontal Microlanguage
    Wesselkamper, 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.
  • Thumbnail Image
    Divided Difference Methods for Finite Fields
    Wesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1975)
    The Reed-Muller Decomposition Theorem is shown to be a special case of a theorem of Newton. Divided difference methods are developed for the general case of any finite field. The Newton Interpolation Theorem is proved for functions of one variable and stated for functions of two variables. Empirical results are given for some two place functions over GF(9) and GF(16).
  • Thumbnail Image
    Divided Difference Methods for Galois Switching Functions
    Wesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1977)
    An alternative is provided to a recently published method of Benjauthrit and Reed for calculating the coefficients of the polynomial expansion of a given function. The method herein is an adaptation to finite fields of a method of Newton. The method is exhibited for functions of one and two variables. The relative advantages and disadvantages of the two methods are discussed. Some empirical results are given for GF(9) and GF(16). It is shown that functions with "don't care" states are represented by a polynomial of minimal degree by this method.
  • Thumbnail Image
    Functionally Complete Machines
    Wesselkamper, 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.
  • Thumbnail Image
    The Logical Foundations of Microlanguages
    Wesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)
    After the consideration of two recent examples of instruction sets for microprogrammable computers, the article sketches known and new results about complete sets of functions which appear to be applicable to microlanguage development. Some needed areas of research are pointed out. Functional completeness is linked to research in control primitives for machines.
  • Thumbnail Image
    A Markov Model of Certain Structured Programs
    Wesselkamper, Thomas C.; Zoladz, Richard W. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1976)
    The paper is concerned with modeling the run time behavior of a certain class of programs. Each program, represented by its flowgraph, is built up from one-in/one-out constructs (after the manner of Dijkstra). The programs have neither transient states nor absorbing states. Each program has one state which possesses two cycles of relatively prime length. A program which possesses these properties is called regular. Such a program may he modeled by a finite Markov chain. It is shown that if a program is regular then its Markov model has a regular transition matrix, that is, the sequence of powers of the transition matrix converges to a matrix all of whose rows are identical. The experimental validity of the method is discussed, as are the implications of the method for program design.
  • Thumbnail Image
    A Markov Model of Cyclic Structured Programs
    Wesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1977)
    The paper defines a class of flow graphs which possess neither absorbing nor transient states. It gives a necessary and sufficient condition that any transition matrix associated with such a program be primitive. With a fixed flowgraph is associated an equivalence class of programs and an equivalence class of transition matrices. The paper investigates the hypothesis that the equivalence class of processes generated by the programs is modeled by the behavior of the equivalence class of eigenvectors generated by the transition matrices. The geometric implications are considered as well as the statistical behavior of the model as applied to the first fourteen algorithms of the Communications of the ACM.
  • Thumbnail Image
    Microprogrammable Cellular Automata
    Muzio, 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.
  • Thumbnail Image
    No Abelian Semigroup Operation Is Complete
    Wesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)
    This paper shows that there does not exist a finite abelian semigroup with order > 3 such that the semigroup operation is complete over S. Neither is {*} complete with constants over S. J. C. Muzio has shown that over any finite space there exists a set of two abelian semigroup operations which is complete with constants over the space. Hence Muzio's result is best possible.
  • Thumbnail Image
    The Requirements for Effective Hardware Description Languages
    Lee, John A. N.; Macock, Deborah Y.; Marks, Peter; Wesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1975)
    The design of hardware description languages (HDL's) is considered with respect to their structural and functional properties rather than their syntactic forms. The contents of an idealized HDL are contrasted with those of nine existing languages, chosen so as to typify a wide range of usage, numerous citations in the literature, and a diversity of source.
  • Thumbnail Image
    Some Classical Mathematical Results Related to the Problems of the Firmware/Hardware Interface
    Wesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1975)
    The paper reviews the Shannon and Reed-Muller Decomposition Theorems and notes the relationship of the former to machine instruction set. It hypothesizes an instruction set based on Galois field operations and applies the divided difference methods of Newton to the automatic generation of a polynomial representation of an arbitrary function. Some numeric results are given for the fields GF(9) and GF(16). An extension of the methods to the representation of functions by rational forms is suggested.
  • Thumbnail Image
    Three Papers on the Completeness Properties of Abelian Semi groups and Groups
    Wesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1974)
    The three papers presented here all arise from recent research into sets of operators which are sufficient to define a horizontal microlanguage for a computer and which are (in some undefined sense) natural for human beings to use. It is this criterion of naturalness which leads us to consider dyadic operators which are commutative and associative, that is, structures which are abelian semigroups.
  • Thumbnail Image
    A Topological Model of the Data Space for a Block Structured Language
    Wesselkamper, 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.
  • Thumbnail Image
    The Uses of Finite Fields
    Wesselkamper, Thomas C. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1976)
    The paper is tutorial in nature, although some of the results are new. It reviews some of the elementary facts about the structure and construction of finite fields and hypothesizes a computer whose fundamental instruction set consists of the Galois field operations. Each total function is shown to be defined by a unique polynomial and this normal representation is also the minimal polynomial representation. A method is presented, due to Newton, for constructing the coefficients of the defining polynomial using divided differences. It is shown that under certain circumstances a total function may be more efficiently evaluated by a rational form with non-zero denominator. Finally a rational form representation is shown to be a natural representation for each partial function. In the light of these considerations the process of producing code for the hypothetical machine is almost entirely automated.
  • Thumbnail Image
    The validity of a Markov model of the behaviour of programs
    Favre, Edward Alfred (Virginia Tech, 1977-05-05)
    In light of the evidence presented, the modified model has been shown to be valid. However, as with any other validation using test cases, the results cannot be considered a truly formal or general proof of its correctness. However they provide grounds for future work attempting to apply the model, which leads to a series of proposals for future endeavours. Rauscher [1] intended that modelling processors be made an integral part of optimizers in translator systems dynamically microprogrammable machines. This is slightly more difficult to achieve automatically with the modified model than with the original one, since DO blocks and termination code must be recognized by the processor, however it is still very feasible. This shows that one useful investigation would be to search for other easily recognizable structures which may be used to reduce the range of transition probabilities generated for the model, thus further improving its accuracy. The modelling process takes a good deal of computing time, so that decreasing the number of sample probability sets generated could tremendously increase the efficiency of the model processor itself with respect to execution time of the optimizer. Further statistical tests should be devised to determine the number of samples necessary for an accurate result. Finally, the model at a stage where techniques should be developed for using it in applications such as optimization by dynamic microprogramming (1], data flow analysis for debugging [21J, and storage allocation in operating systems using paging. For all of these applications, knowledge of the relative frequency of code blocks is not enough, other information must be attached to the states of the model before it may applied to the problem. When dealing with the optimization of execution me, the execution time of the code in each block is needed. For data flow analysis and storage allocation purposes, a table of the variables used in each block and their attributes is necessary. All of this makes the author feel that there is still much work to be done with this Markov Model of Program Behaviour.