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