Hashing techniques for accessing a table without searching it are usually designed to perform efficiently on the average over all possible contents of the table. If the table contents are known in advance, we might be able to choose a hashing function with guaranteed efficient (worst-case) performance. Such a technique has been called “perfect hashing” by Sprugnoli and others. In this paper, we address the question of whether perfect hashing is feasible in principle as a general technique, or whether it must rely on special qualities of the table contents. We approach the question by counting the number of functions which must be searched to be sure of finding a perfect hashing function. We present upper and lower bounds on the size of this search space, with attention to the tradeoff between the size of the search space and the size of the hash table.

Abstract This paper summarizes a project whose goal is the implementation of a useful interpreter for abstract equations that is absolutely faithful to the logical semantics of equations. The interpreter was first distributed to Berkeley UNIX VAX sites in May 1983. The main novelties of the interpreter are strict adherence to semantics based on logical consequences, ‘lazy’ (outermost) evaluation applied uniformly, an implementation based on table‐driven pattern matching, with no run‐time penalty for large sets of equations, and strict separation of syntactic and semantic processing, so that different syntaxes may be used for different problems.

Ω(n log n) time is required to sort n integers using comparison, addition, subtraction, multiplication, division, indirect addressing, and mildly restricted truncation.

This paper summarizes a project, introduced in [HO79, HO82b], whose goal is the implementation of a useful interpreter for abstract equations that is absolutely faithful to the logical semantics of equations. The Interpreter was first distributed to Berkeley UNIX VAX sites in May, 1983. The main novelties of the interpreter are

Typed lambda (?`-) calculi provtde convement mathematical settings in which to investigate the effects of type structure on the function definmon mechamsm m programming languages.Lambda expressaons mtm~c programs that do not use while loops or carcular function definitions.Two typed ?`-calculi are investigated, the sunply typed ?`-calculus, whose types are similar to Pascal types, and the second-order typed ?,-calculus, which has a type abstractaon mechamsm simdar to that of modern data abstraction languages such as ALPHARD.Two related questions are considered for each calculus: (1) What functaons are definable m the calculus?and (2) How difficult is the proof that all expressions in the calculus are normahzable 0.e., that all computaUons termmate)* The simply typed calculus only defines elementary functtons.Normahzation for this calculus ~s provable using commonplace forms of reasoning formalazable m Peano arithmetic The second-order calculus defines a huge hierarchy of funcuons going far beyond Ackermann's function These funcuons are so rapidly increasing that Peano arithmetic cannot prove that they are total In fact, normalizataon for the second-order calculus cannot be proved even m second-order Peano artthmetic, nor m Peano anthmettc augmented by all true statements Also d~scussed are the lmphcataons of the present ?`-calculusresults for the programming languages PASCAL, ALPHARD, RUSSELL, and MODEL.

ABSTgACT.Tree pattern matching is an interesting special problem which occurs as a crucial step m a number of programmmg tasks, for instance, design of interpreters for nonprocedural programming languages, automatic implementations of abstract data types, code optimization m compilers, symbohc computation, context searching in structure editors, and automatic theorem provmg.As with the sorting problem, the variations in requirements and resources for each application seem to preclude a uniform, umversal solution to the tree-pattern-matching problem.Instead, a collection of well-analyzed techmques, from which specific applications may be selected and adapted, should be sought.Five new techniques for tree pattern matching are presented, analyzed for time and space complexity, and compared with previously known methods.Particularly important are applications where the same patterns are matched against many subjects and where a subject may be modified incrementally Therefore, methods which spend some tune preprocessmg patterns in order to improve the actual matching time are included Categories and SubJect Descriptors' F.2.2 [Analysis of Algorithms and Problem Complexity]' Nonnutactical Algorithms and Problems--pattern matchmg, G 2 2 [Discrete Mathematics]: Graph Theory--trees

Efficient algorithms are presented for two geometric problems. Both problems involve finding the best projection of a set of points from two-space onto a line, with two different notions of “best”. The key technique is to identify critical angles in between which the functions to be optimized have nice trigonometric forms that can be solved exactly. Applications to hashing arise when we look for the best linear combination of two hashing functions.

The augmented data manipulator (ADM) [5] has been proposed as an interconnection scheme for microprocessors. In this note we show how the number of permutations achieved by the last stage of an n-node ADM may be derived from a Fibonacci series. This result was used in [1] to analyze the total number of permutations achieved by an entire ADM.

Equations provide a convenient notation for defining many computations, for example, for programming language interpreters.This paper illustrates the usefulness of equational programs, describes the problems involved in implementing equational programs, and investigates practical solutions to those problems.The goal of the study is a system to automatically transform a set of equations into an efficient program which exactly implements the logical meaning of the equations.This logical meaning may be defined in terms of the traditional mathematical interpretation of equations, without using advanced computing concepts._

Equations provide a rich, intuitively understandable notation for describing nonprocedural computing languages such as LISP and Lucid. In this paper, we present techniques for automatically generating interpreters from equations, analagous to well-known techniques for generating parsers from context-free grammars. The interpreters so generated are exactly faithful to the simple traditional mathematical meaning of the equations-no lattice-theoretic or fixpoint ideas are needed to explain the correspondence. The main technical problem involved is the extension of efficient practical string matching algorithms to trees. We present some new efficient table-driven matching techniques for a large class of trees, and point out unsolved problems in extending this class. We believe that the techniques of this paper form the beginnings of a useful discipline of interpreting, comparable to the existing discipline of parsing.

Strongly typed programming languages contain a natural subrecursive part consisting of programs with no loops and no explicitly recursive (circular) function definitions. For languages with polymorphic type structure, such as Model, the termination of all loop-free nonrecursive programs is independent of Peano Arithmetic. An attempt to apply the same techniques to prove independence of the [email protected]@@@NP problem can succeed only if NP complete problems have almost polynomial complexity.