An approach to designing very fast algorithms for approximate string matching in a dictionary is proposed. Multiple spelling errors corresponding to insert, delete, change, and transpose operations on character strings are considered in the fault model. The design of very fast approximate string matching algorithms through a four-step reduction procedure is described. The final and most effective step uses hashing techniques to avoid comparing the given word with words at large distances. The technique has been applied to a library book catalog textbase. The experiments show that performing approximate string matching for a large dictionary in real-time on an ordinary sequential computer under our multiple fault model is feasible.>

VAR, a transformational approach for obtaining multilevel logic synthesis results, is described. Suppressed variable permutation and complementation (SVPC) transformations which are powerful and can be economically realized are introduced. Each SVPC transformation can be viewed as an identity mapping on the n-cube, except on an (n-r)-subcube (defined by r fixed coordinates), where it behaves like a variable permutation and complementation (VPC) transformation on n-r variables (the free variables). VAR is based on transforming the input functions to predefined goal functions by SVPC transformations. A transformation tree is obtained, and the transformations on the tree are collapsed and further simplified to obtain an economical circuit. This approach is illustrated by considering the sum function of the full adder.>

A syntax-directed translator has been implemented to translate Prolog programs from Arity dialect into Quintus dialect. A comparison of the features of the two dialects, the strategies used in writing the translator, and the implementation considerations are described. Experience gained by using the translator to port an Arity version of FAIRS, an information retrieval system, to a VAX Unix environment is presented.>

The development of program slicers with respect to programs containing recursive procedures, is investigated. A theoretical foundation is constructed for the computation process. A general recursive scheme is introduced as a basis of discussion. A complete slice is defined for recursive procedures to identify clearly what can be obtained through static analysis. The 'everywhere undefined function' Omega introduced by the authors provides the required starting condition for the computation process, and a fixed-point equation supplies a terminating condition such that the computation will have a definite end point. The poset theory is used to verify the entire process. The implementation of the proposed technique is discussed. >

In this paper, we shall derive two formulas for the average number of buckets to be examined over all possible partial match queries for Cartesian product files and random files, respectively. The superiority of the Cartesian product file is established. A new multi-key file, called a partition file, is introduced. It is shown that both Cartesian product files and random files are special cases of partition files.

A new approach is proposed for the design of perfect hash functions. The algorithms developed can be effectively applied to key sets of large size. The basic ideas employed in the construction are rehash and segmentation. Analytic results are given which are applicable when problem sizes are small. Extensive experiments have been performed to test the approach for problems of larger size.

In this paper, we shall show that the symbolic Gray code hashing mechanism is not only good for best matching, but also good for partial match queries. Essentially, we shall propose a new hashing scheme, called bucket-oriented symbolic Gray code, which can be used to produce any arbitrary Cartesian product file, which has been shown to be good for partial match queries. Many interesting properties of this new multiattribute hashing scheme, including the property that it is a perfect hashing scheme, have been discussed and proved.