Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 37 Issue 4, Oct. 1990

Patricia tries again revisited
Wojciech Szpankowski
Pages: 691-711
DOI: 10.1145/96559.214080
The Patricia trie is a simple modification of a regular trie. By eliminating unary branching nodes, the Patricia achieves better performance than regular tries. However, the question is: how much on the average is the Patricia better? This paper...

A correction of the termination conditions of the Henschen-Naqvi technique
David A. Briggs
Pages: 711-719
DOI: 10.1145/96559.96562
Henschen and Naqvi described a technique for translating queries on recursively defined relations of a Datalog database into iterative programs that invoke a query processor for conventional select-project-join queries of the relational algebra....

Early stopping in Byzantine agreement
Danny Dolev, Ruediger Reischuk, H. Raymond Strong
Pages: 720-741
DOI: 10.1145/96559.96565
Two different kinds of Byzantine Agreement for distributed systems with processor faults are defined and compared. The first is required when coordinated actions may be performed by each participant at different times. This kind is called...

Unification in primal algebras, their powers and their varieties
Tobias Nipkow
Pages: 742-776
DOI: 10.1145/96559.96569
This paper examines the unification problem in the class of primal algebras and the varieties they generate. An algebra is called primal if every function on its carrier can be expressed just in terms of the basic operations of...

Higher-order Horn clauses
Gopalan Nadathur, Dale Miller
Pages: 777-814
DOI: 10.1145/96559.96570
A generalization of Horn clauses to a higher-order logic is described and examined as a basis for logic programming. In qualitative terms, these higher-order Horn clauses are obtained from the first-order ones by replacing first-order terms with...

Decision tree reduction
J. R. B. Cockett, J. A. Herrera
Pages: 815-842
DOI: 10.1145/96559.96576
The reduction algorithm is a technique for improving a decision tree in the abseence of aproecise cost criterion. The result of applying the algorithm is an irreducible tree that is no less efficient than the original, and may be more...

Convex separable optimization is not much harder than linear optimization
D. S. Hochbaum, J. George Shanthikumar
Pages: 843-862
DOI: 10.1145/96559.96597
The polynomiality of nonlinear separable convex (concave) optimization problems, on linear constraints with a matrix with “small” subdeterminants, and the polynomiality of such integer problems, provided the inteter linear version of...

The representation of multistage interconnection networks in queuing models of parallel systems
Peter G. Harrison
Pages: 863-898
DOI: 10.1145/96559.96599
A major component of a parallel machine is its interconnection network (IN), which provides concurrent communication between the processing elements. It is common to use a multistage interconnection network (MIN) that is constructed using...