Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 33 Issue 2, April 1986

Equality-based binary resolution
Vincent J. Digricoli, Malcolm C. Harrison
Pages: 253-289
DOI: 10.1145/5383.5389
A major event in automated reasoning was the introduction by Robinson of resolution as an inference principle that is complete for the first-order predicate calculus. Here the theory of binary resolution, based strictly on unification, is recast...

Partitioning a polygonal region into trapezoids
Takao Asano, Tetsuo Asano, Hiroshi Imai
Pages: 290-312
DOI: 10.1145/5383.5387
The problem of partitioning a polygonal region into a minimum number of trapezoids with two horizontal sides is discussed. A triangle with a horizontal side is considered to be a trapezoid with two horizontal sides one of which is degenerate....

The mutual exclusion problem: part I—a theory of interprocess communication
Leslie Lamport
Pages: 313-326
DOI: 10.1145/5383.5384
A novel formal theory of concurrent systems that does not assume any atomic operations is introduced. The execution of a concurrent program is modeled as an abstract set of operation executions with two temporal ordering relations:...

The mutual exclusion problem: partII—statement and solutions
Leslie Lamport
Pages: 327-348
DOI: 10.1145/5383.5385
The theory developed in Part I is used to state the mutual exclusion problem and several additional fairness and failure-tolerance requirements. Four “distributed” N-process solutions are given, ranging from a...

A sound and sometimes complete query evaluation algorithm for relational databases with null values
Raymond Reiter
Pages: 349-370
DOI: 10.1145/5383.5388
A sound and, in certain cases, complete method is described for evaluating queries in relational databases with null values where these nulls represent existing but unknown individuals. The soundness and completeness results are proved relative...

Partial match retrieval of multidimensional data
Philippe Flajolet, Claude Puech
Pages: 371-407
DOI: 10.1145/5383.5453
A precise analysis of partial match retrieval of multidimensional data is presented. The structures considered here are multidimensional search trees (k-d-trees) and digital tries (k-d-tries), as well as...