**The complexity of logic-based abduction**

Thomas Eiter, Georg Gottlob

Pages: 3-42

DOI: 10.1145/200836.200838

Abduction is an important form of nonmonotonic reasoning allowing one to find explanations for certain symptoms or manifestations. When the application domain is described by a logical theory, we speak about logic-based...

**Reasoning about temporal relations**: a maximal tractable subclass of Allen's interval algebra

Bernhard Nebel, Hans-Jürgen Bürckert

Pages: 43-66

DOI: 10.1145/200836.200848

We introduce a new subclass of Allen's interval algebra we call “ORD-Horn subclass,” which is a strict superset of the “pointisable subclass.” We prove that reasoning in the ORD-Horn subclass is a polynomial-time problem...

**A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields**

Paul B. Callahan, S. Rao Kosaraju

Pages: 67-90

DOI: 10.1145/200836.200853

We define the notion of a well-separated pair decomposition of points in d-dimensional space. We then develop efficient sequential and parallel algorithms for computing such a decomposition. We apply the...

**Planar-adaptive routing**: low-cost adaptive networks for multiprocessors

Andrew A. Chien, Jae H. Kim

Pages: 91-123

DOI: 10.1145/200836.200856

Network throughput can be increased by allowing multipath, adaptive routing. Adaptive routing allows more freedom in the paths taken by messages, spreading load over physical channels more evenly. The flexibility of adaptive routing introduces...

**Sharing memory robustly in message-passing systems**

Hagit Attiya, Amotz Bar-Noy, Danny Dolev

Pages: 124-142

DOI: 10.1145/200836.200869

Emulators that translate algorithms from the shared-memory model to two different message-passing models are presented. Both are achieved by implementing a wait-free, atomic, single-writer multi-reader register in unreliable, asynchronous...

**Dynamic fault-tolerant clock synchronization**

Danny Dolev, Joseph Y. Halpern, Barbara Simons, Ray Strong

Pages: 143-185

DOI: 10.1145/200836.200870

This paper gives two simple efficient distributed algorithms: one for keeping clocks in a network synchronized and one for allowing new processors to join the network with their clocks synchronized. Assuming a fault-tolerant authentication...

**Constructing 1-writer multireader multivalued atomic variables from regular variables**

S. Haldar, K. Vidyasankar

Pages: 186-203

DOI: 10.1145/200836.200871

A simple wait-free construction of 1-writer multireader multivalued atomic variable from multireader regular variables is presented in this paper. A key point of the construction is the use of an elegant forwarding technique to overcome the...

**Bounds on the speedup and efficiency of partial synchronization in parallel processing systems**

C. S. Chang, R. Nelson

Pages: 204-231

DOI: 10.1145/200836.200872

In this paper, we derive bounds on the speedup and efficiency of applications that schedule tasks on a set of parallel processors. We assume that the application runs an algorithm that consists of N iterations and before...

**Bisimulation can't be traced**

Bard Bloom, Sorin Istrail, Albert R. Meyer

Pages: 232-268

DOI: 10.1145/200836.200876

In the concurrent language CCS, two programs are considered the same if they are bisimilar. Several years and many researchers have demonstrated that the theory of bisimulation is mathematically appealing and useful in practice....

**Designing programs that check their work**

Manuel Blum, Sampath Kannan

Pages: 269-291

DOI: 10.1145/200836.200880

A program correctness checker is an algorithm for checking the output of a computation. That is, given a program and an instance on which the program is run, the checker certifies whether the output of the program on that...