Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 41 Issue 2, March 1994

Faster tree pattern matching
Moshe Dubiner, Zvi Galil, Edith Magen
Pages: 205-213
DOI: 10.1145/174652.174653

Biconnectivity approximations and graph carvings
Samir Khuller, Uzi Vishkin
Pages: 214-235
DOI: 10.1145/174652.174654
A spanning tree in a graph is the smallest connected spanning subgraph. Given a graph, how does one find the smallest (i.e., least number of edges) 2-connected spanning subgraph (connectivity refers to both edge and vertex connectivity, if not...

Equational inference, canonical proofs, and proof orderings
Leo Bachmair, Nachum Dershowitz
Pages: 236-276
DOI: 10.1145/174652.174655
We describe the application of proof orderings—a technique for reasoning about inference systems-to various rewrite-based theorem-proving methods, including refinements of the standard Knuth-Bendix completion procedure based on critical...

Tight lower bounds for probabilistic solitude verification on anonymous rings
Karl Abrahamson, Andrew Adler, Lisa Highám, David Kirkpatrick
Pages: 277-310
DOI: 10.1145/174652.174656
A model that captures communication on asynchronous unidirectional rings is formalized. Our model incorporates both probabilistic and nondeterministic features and is strictly more powerful than a purely probabilistic model. Using this model, a...

The elusive atomic register
Ambuj K. Singh, James H. Anderson, Mohamed G. Gouda
Pages: 311-339
DOI: 10.1145/174652.174657
We present a construction of a single-writer, multiple-reader atomic register from single-writer, single-reader atomic registers. The complexity of our construction is asymptotically optimal; O(M2 + MN)...

Reasoning about knowledge and probability
Ronald Fagin, Joseph Y. Halpern
Pages: 340-367
DOI: 10.1145/174652.174658

An analysis of ML typability
A. J. Kfoury, J. Tiuryn, P. Urzyczyn
Pages: 368-398
DOI: 10.1145/174652.174659
We carry out an analysis of typability of terms in ML. Our main result is that this problem is DEXPTIME-hard, where by DEXPTIME we mean DTIME(2n0(1)). This, together with the known exponential-time...

Optimal algorithms for parallel Givens factorization on a coarse-grained PRAM
Michel Cosnard, El Mostafa Daoudi
Pages: 399-421
DOI: 10.1145/174652.174660

Parallel linear programming in fixed dimension almost surely in constant time
Noga Alon, Nimrod Megiddo
Pages: 422-434
DOI: 10.1145/174652.174661
For any fixed dimension d, the linear programming problem with n inequality constraints can be solved on a probabilistic CRCW PRAM with O...