**Provably correct theories of action**

Fangzhen Lin, Yoav Shoham

Pages: 293-320

DOI: 10.1145/201019.201021

We investigate logical formalization of the effects of actions in the situation calculus. We propose a formal criterion against which to evaluate theories of deterministic actions. We show how the criterion provides us a formal foundation upon...

**A randomized linear-time algorithm to find minimum spanning trees**

David R. Karger, Philip N. Klein, Robert E. Tarjan

Pages: 321-328

DOI: 10.1145/201019.201022

We present a randomized linear-time algorithm to find a minimum spanning tree in a connected graph with edge weights. The algorithm uses random sampling in combination with a recently discovered linear-time algorithm for verifying a minimum...

**Decomposition of magic rewriting**

Ke Wang, Weining Zhang, Siu-Cheung Chau

Pages: 329-381

DOI: 10.1145/201019.201027

The magic rewriting focuses on relevant data but suffers from additional rules, predicates, and tuples that are generated in search for the relevant data. Reducing the arity of predicates can cut down the number of such rules, predicates, and...

**On the average communication complexity of asynchronous distributed algorithms**

John N. Tsitsiklis, George D. Stamoulis

Pages: 382-400

DOI: 10.1145/201019.201029

We study the communication complexity of asynchronous distributed algorithms. Such algorithms can generate excessively many messages in the worst case. Nevertheless, we show that, under certain probabilistic assumptions, the expected number of...

**The isomorphism conjecture fails relative to a random oracle**

Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

Pages: 401-420

DOI: 10.1145/201019.201030

**NP trees and Carnap's modal logic**

Georg Gottlob

Pages: 421-457

DOI: 10.1145/201019.201031

In this paper we consider problems and complexity classes definable by interdependent queries to an oracle in NP. How the queries depend on each other is specified by a directed graph G. We first study the class of problems where G is a general...

**Three logics for branching bisimulation**

Rocco De Nicola, Frits Vaandrager

Pages: 458-487

DOI: 10.1145/201019.201032

Three temporal logics are introduced that induce on labeled transition systems the same identifications as branching bisimulation, a behavioral equivalence that aims at ignoring invisible transitions while preserving the branching structure of...

**Las Vegas algorithms for linear and integer programming when the dimension is small**

Kenneth L. Clarkson

Pages: 488-499

DOI: 10.1145/201019.201036

This paper gives an algorithm for solving linear programming problems. For a problem with n constraints and d variables, the algorithm requires an expectedOd^{2}n+...

**Nearly optimal algorithms and bounds for multilayer channel routing**

Bonnie Berger, Martin Brady, Donna Brown, Tom Leighton

Pages: 500-542

DOI: 10.1145/201019.201037

This paper presents algorithms for routing channels with L≥2 layers. For the unit vertical overlap model, we describe a two-layer channel routing algorithm that uses at most d+O...