Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 42 Issue 2, March 1995

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 expectedOd2n+...

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