Suppose that we are given a vector consisting of only 1's and 0's and we are interested in finding some special properties of this vector. For instance, we like to determine whether all of the bits from location s to location e in the vector are all 1's or whether there exists a 1 from location s to location e. In more complicated cases, we are given two bit-vectors and we like to investigate the mutual properties between the two vectors. For instance, we want to find all locations i in vector B such that there exists a k in vector A, k≤i, such that A(k)=1 and in vector B, locations from k to i all assume value 1. These problems all involve ‘for-all’ or ‘there-exists’ notations and can of course be solved by sequential programs. In this paper, we are interested in bit-parallel process to solve these problems. That is, we are interested in solving the problem efficiently by using ‘bitwise-and’, ‘bitwise-or’ and other bitwise logical operations. A sequence of logical operations can be expressed as a logical formula. This paper proposes a systematical method to find such logical formulas to solve problems involving bit-vectors with ‘for-all’ and ‘there-exists’ notations. Five logical prototype problems, named ‘single-for-all’ (1's), ‘single-there-exists’, ‘multiple-for-all’, ‘multiple-there-exists’ and ‘multiple-there-exists-and-for-all’, are defined in this paper. For each problem, we show that there exists a corresponding logical formula that can be computed using bit-parallel operations in O(n/w) time, where w is the word size of the machine. We also propose four variants for these five problems, and show that their logical formulas can be obtained using those of the five prototype problems.

In this paper, we deal with the exact circular string matching problem (abbreviated as ECSM). Given a string P = p1p2 ⋯ pm, a string P(i) = pipi+1 ⋯ pmp1 ⋯ pi−1, for 1 ≤ i ≤ m, is a circular string of P. Given a text string T = t1t2 ⋯ tn and a pattern P, the ECSM problem is to find all occurrences of P(i) in text T for 1 ≤ i ≤ m. This paper proposes two algorithms that perform searching of a circular string on text using the bit-parallel technique. Our algorithms use only the composition of bitwise-logical operations and basic arithmetic operations, and apply this technique to solve the problem. These algorithms are given names CSBNDM and CSBNDNq, respectively. We give several experiments to verify that they have good performance for random strings and DNA sequences.

In computational molecular biology, genome rearrangement is a fundamental important problem: Given two sequences representing two species, compute a smallest series of a specific operation for transforming a sequence to another sequence. We could have some insight as how far away genetically these species from genome rearrangement. There are different problems according to distinct operations such as sorting by reversals, sorting by transpositions and so on. In this paper, we proposed the concept of the increasing substring, and presented an approach based upon the first increasing substring for sorting by transpositions.

Summary form only given. Visual displaying techniques have existed for a rather long time. In this talk, we shall show how the visual display techniques can be used to help biological analyze data. Furthermore, we shall show that the multi-dimensional scaling technique is a very useful tool to rotate protein 3-dimensional structures so that comparisons can be easily made on them, In other words, the similarity between two protein structures can be quickly determined after the rotation is done by the multidimensional scaling technique. We shall also show that we have successfully applied a relaxation method to the RNA folding problem. Given the logical structure of an RNA sequence, we can use the relaxation method to find the RNA physical structure.

The paper first shows that the bucket allocation problem of an MKH (multiple key hashing) file for partial match retrieval can be reduced to that of a smaller sized subfile, called the remainder of the file. And it is pointed out that the remainder type MKH file is the hardest MKH file for which to design an optimal allocation scheme. The authors then particularly concentrate on the allocation of an important remainder type MKH file; namely, the k-ary MKH file. They present various sufficient conditions on the number of available disks and the number of attributes for a k-ary MKH file to have a perfectly optimal allocation among the disks for partial match queries. Based upon these perfectly optimal allocations, they further present a heuristic method, called the CH (cyclic hashing) method, to produce near optimal allocations for the general k-ary MKH files. Finally, a comparison, by experiment, between the performances of the proposed method and an "ideal" perfectly optimal method, shows that the CH method is indeed satisfactorily good for the general k-ary MKH files.

We are concerned with the problem of designing optimal linear hashing files for orthogonal range retrieval. Through the study of performance expressions, we show that optimal basic linear hashing files and optimal recursive linear hashing files for orthogonal range retrieval can be produced, in certain cases, by a greedy method called the MMI (minimum marginal increase) method; and it is pointed out that optimal linear hashing files for partial match retrieval need not be optimal for orthogonal range retrieval.

A new public-key (two-key) cipher scheme is proposed in this paper. In our scheme, keys can be easily generated. In addition, both encryption and decryption procedures are simple. To encrypt a message, the sender needs to conduct a vector product of the message being sent and the enciphering key. On the other hand, the receiver can easily decrypt it by conducting several multiplication operations and modulus operations. For security analysis, we also examine some possible attacks on the presented scheme.>

Isomorphism relations are utilized to analyze the Hopfield associative memory. When the number of fundamental memories m=/<3, it is proved that two Hopfield associative memories are isomorphic if they have the same mutual distances between the fundamental memories. The number of stable states and the synchronous convergence time of a Hopfield associative memory are shown to be less than or equal to 2 to the power 2(m-1) and 4 to the power 2(m-1), respectively, where m>/=1.

The encryption/decryption scheme proposed in8 is generalised in this paper. The new cryptosystem presented is record-oriented, i.e. each record is encrypted integratedly with different keys and each field is decrypted individually by separate keys, and has significant advantages over many conventional methods. Compared to the encryption system proposed by Davida, Wells, and Kam,8 this new system has the advantages the previous one has and improves two drawbacks of theirs which will be stated below. Thus not only the security is increased but also the storage needed is reduced in the new cryptosystem.

Consideration is given to the following problem. Preprocess n moving points in a plane, such that the Euclidean minimum spanning tree of these points at a given time t can be reported efficiently. In the result, if the moving points are in k-motion, after an O(kn/sup 4/ log n) time preprocessing step and using O(m) space to store the preprocessing result, the Euclidean minimum spanning tree at t can be reported in O(n) time, where m denotes the number of changes of the Euclidean minimum spanning tree of these points from time t=0 to time t= infinity .>

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.>

Relations of stable states between different Hopfield neural nets are shown, and upper bounds to their transient lengths are given. The proofs of the results lie in examining the sinks and the maximum path length of the state transition graph. IfWis the weight matrix of a Hopfield associative memory determined frommreference patterns, the experiments showed thatPmax(G(W,Θ)) is of order O(mn) andTord(GB(W,Θ))=2 whenm=1 or 2, for alln⩾3, wherenis the size of the net and Θ is zero factor

A fast parallel algorithm, which is generalized from the parallel algorithms for solving banded linear systems, is proposed to solve sparse triangular systems. The original problem is transformed into a directed graph. The solving procedure then consists of eliminating edges in this graph. The worst-case time-complexity of this parallel algorithm is O(log/sup 2/n) where n is the size of the coefficient matrix. When the coefficient matrix is a triangular banded matrix with bandwidth m, then the time-complexity of the algorithm is O(log(m)*log(n)).>

An algorithm known as optimal channel routing (OCR) is proposed which finds an optimal solution for the channel routing problem in VLSI design. The algorithm is an A* algorithm with good heuristics and dominance rules for terminating unnecessary nodes in the searching tree. Experimental results, agreeing with theoretical analysis, show that it behaves quite well in average cases. An optimal solution is obtained for the Deutsch difficult case in 5.5-min-CPU time after the algorithm is implemented in Pascal and run on a VAX 11/750 computer.>

Some common guidelines that can be used to design parallel algorithms under the single-channel broadcast communication model are presented. Several graph problems are solved, including topological ordering, the connected component problem, breadth-first search, and depth-first search. If an ideal conflict resolution scheme is used, all of the algorithms require O(n) time by using n processors. Under such a situation, the algorithms are all optimal. If a realistic conflict resolution is used, the algorithms require O(n log n) time by using n/log n processors. For both cases, all of the algorithms achieve optimal speedups.>

An O(n log log n) algorithm is proposed for minimally rectangular partitioning a simple rectilinear polygon. For any simple rectilinear polygon P, a vertex-edge visible pair is a vertex and an edge that can be connected by a horizontal or vertical line segment that lies entirely inside P. It is shown that, if the vertex-edge visible pairs are found, the maximum matching and the maximum independent set of the bipartite graph derived from the chords of a simple rectilinear polygon can be found in linear time without constructing the bipartite graph. Using this algorithm, the minimum partition problem for convex rectilinear polygons and vertically (horizontally) convex rectilinear polygons can be solved in O(n) time.>

Article Free AccessMinimum partitioning simple rectilinear polygons in O(n log log n) - time Authors: W. T. Liou Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, R.O.C. Institute of Computer Science, National Tsing Hua University, Hsinchu, Taiwan, R.O.C.View Profile , J. J. Tan Institute of Information Science, National Chiao Tung University, Hsinchu, Taiwan, R.O.C. Institute of Information Science, National Chiao Tung University, Hsinchu, Taiwan, R.O.C.View Profile , R. C. Lee National Tsing Hua University, Hsinchu, Taiwan, and the Academia Sinica, Taipei, Taiwan, R.O.C. National Tsing Hua University, Hsinchu, Taiwan, and the Academia Sinica, Taipei, Taiwan, R.O.C.View Profile Authors Info & Claims SCG '89: Proceedings of the fifth annual symposium on Computational geometryJune 1989 Pages 344–353https://doi.org/10.1145/73833.73871Published:05 June 1989Publication History 13citation1,034DownloadsMetricsTotal Citations13Total Downloads1,034Last 12 Months120Last 6 weeks20 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The authors consider upper bounds on the number of intersections between two rectangular paths. Let these two paths be denoted as P and Q, and denote the number of Manhattan subpaths in P and Q by mod P mod and mod Q mod respectively. K. Kant (1985) gave an upper bound of 10 mod P mod mod Q mod /9+4( mod P mod + mod Q mod )/9. The authors have sharpened these upper bounds, using methods to break the rectangular paths into subpaths, to be mod P mod mod Q mod +( mod P mod /2)+( mod Q mod /3), where they assume without loss of generality that mod P mod>

In this paper, we shall present a parallel algorithm to perform nonlinear mapping which is useful for clustering analysis and pattern recognition. This parallel nonlinear mapping algorithm is slightly different from the original nonlinear mapping algorithm. Experimental results show that our parallel nonlinear mapping algorithm works quite well.

In this paper, we shall describe a minimal perfect hashing scheme suitable for letter-oriented keys. We successfully applied this minimal perfect hashing function to four non-trivial set of keys: 12 months in English, 34 non-printable ASCII identifiers, 31 most frequently used English words and 36 Pascal reserved words.

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.

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.

In this paper, we first introduced the concept of Cartesian product files. We then derived a formula for random files. A computer simulation experiment was performed to compare these two files. So far as shown by the experimental results, the Cartesian product file concept was indeed a good one. We also showed that the problem of designing an optimal Cartesian product file was partially related to the problem of finding a minimal N-tuple. A method to find minimal N-tuples was presented and its properties were discussed.

In this paper, we extend the binary Gray code to symbolic Gray code. We then show that this symbolic Gray code can be used as a multikey hashing function for storing symbolic records. The record stored at location k and the record stored at location k + 1 will be nearest neighbors if this hashing function is used. Thus, this symbolic Gray code hashing function exhibits some kind of clustering property which will group similar records together. This property is a desirable property for designing nearest neighbor searching (also called best match searching) systems. There are many other interesting properties of this hashing function. For instance, there exists an address-to-key transformation which can be used to determine the record stored at certain location k if this hashing function is used. Besides, if there are totally M records, we only have to reserve exactly M locations; there are no collisions and wasting of memory storage. At the end of this paper, it is shown that the resulting file exhibits the multiple-attribute tree structure.

This paper results from an attempt to unify several different file system design theories. We define a term "partial match pattern" and show that in order to produce file systems optimal with respect to partial match patterns, both the multikey hashing (MKH) method [16] and the multidimensional directory (MDD) method [11] must be in such a form that the number of subdivisions is the same for all domains of keys. We show the conditions for the string homomorphism hashing (SHH) method [15], the MKH method, and the MDD method to be equivalent to one another. We define the so-called Cartesian product files and show that if all records are present, the records in a Cartesian product file form a shortest spanning path in which the Hamming distance between every pair of consecutive records is 1. Thus the SHH method, the MKH method, the MDD method, and the multikey sorting (MKS) method [10] are linked together. Finally, we show that for both partial and best match queries, the file systems exhibit a common characteristic: similar records are grouped together.

All of the existing nearest neighbor searching techniques divide the searching into two parts: A global searching and a local searching. In order to minimize the number of records to be examined, the global searching must be a very sophisticated one such that the initial local searching will be confined to a very small region. This kind of global searching is usually very time-comsuming. In this paper, we propose the use of hash coding to guide the global search. Given a record, we hash it to an address and the initial searching is to be started by searching records stored in that address. We believe that our method is efficient because hashing is easy to implement and fast to execute. In other words, if our method is used, the global searching time will be very short.

We computer scientists face at least two problems in promoting the use of computerized data-base systems: 1) some important data might be missing; 2) there might be errors in the data. Both of these problems can be quite serious. If they cannot be solved, it will be quite hard to convince potential users that computerized information systems are useful.

It is often possible to save storage space in a computer by storing only the differences among data items rather than the entire items. For example, suppose we have two records A and B. We should store all of A, then for B store a pointer to A and the differences between A and B. If A and B are similar, there will be few differences and storage space can be saved.

A method for the sequential mapping of points in a high-dimensional space onto a plane is presented. Whenever a new point is mapped, its distgnces to two points previously mapped are exactly preserved. On the resulting map, 2M -3 of the original distances can be exactly preserved. The mapping is based on the distances of a minimal spanning tree constructed from the points. All of the distances on the minimal spanning tree are exactly preserved.

In this paper, we shall introduce a concept widely used by statisticians, the principal component analysis technique. We shall show that this principal component analysis technique can be used to create new keys from a set of old keys. These new keys are very useful in narrowing down the search domain. We shall also show that the projections on the first principal component direction can be viewed as hashing addresses for the best-match searching problem.

Suppose a program P is written to accept a set of inputs I. If we are only interested in a nonempty subset $I^ * $ of I, we usually can simplify P to another program $P^ * $ such that $P^ * $ runs faster on $I^ * $ than P does. The problem of specialization is to find such $P^ * $. In this paper, the program P and the input $I^ * $ will be specified by axioms. Using these axioms, we can obtain $P^ * $ from P through theorem-proving techniques.

A relaxation method mapping high-dimensional sample points to low-dimensional sample points is discussed. This method tries to preserve the local interdistance of sample points. Some special heuristics have been introduced to handle the difficulty arising from a large amount of data. Experimental results with handwritten character data and Iris data show that the method runs fast, converges rapidly, and requires a small amount of memory space.

article Free Access Share on Fuzzy Logic and the Resolution Principle Author: Richard C. T. Lee National Institutes of Health, Heuristics Laboratory, Division of Computer Research and Technology, Department of Health, Education and Welfare, Bethesda, Maryland National Institutes of Health, Heuristics Laboratory, Division of Computer Research and Technology, Department of Health, Education and Welfare, Bethesda, MarylandView Profile Authors Info & Claims Journal of the ACMVolume 19Issue 1Jan. 1972 pp 109–119https://doi.org/10.1145/321679.321688Published:01 January 1972Publication History 236citation1,107DownloadsMetricsTotal Citations236Total Downloads1,107Last 12 Months82Last 6 weeks20 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper is concerned with efficient ways to find optimal solutions to AND/OR graphs.Although the general methods are still at large, we have found an efficient way to obtain optimal solutions to AND/OR series-parallel graphs.This is achieved by reducing an AND/OR series-parallel graph to an AND/OR tree.Once a graph is reduced to a tree, all the known exact and heuristic methods of tree searching can be applied.

This paper describes an algorithm which will generate all the prime implicants of a Boolean function. The algorithm is different from those previously given in the literature, and in many cases it is more efficient. It is proved that the algorithm will find all the prime implicants. The algorithm may possibly generate some nonprime implicants. However, using frequency orderings on literals, the experiments with the algorithm show that it usually generates very few ( possibly none) nonprime implicants. Furthermore, the algorithm may be used to find the minimal sums of a Boolean function. The algorithm is implemented by a computer program in the LISP language.