Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 41 Issue 1, Jan. 1994

Fishspear: a priority queue algorithm
Michael J. Fischer, Michael S. Paterson
Pages: 3-30
DOI: 10.1145/174644.174645
The Fishspear priority queue algorithm is presented and analyzed. Fishspear is comparable to the usual heap algorithm in its worst-case running time, and its relative performance is much better in many common situations. Fishspear also differs...

Efficient computation of Fourier inversion for finite groups
Daniel N. Rockmore
Pages: 31-66
DOI: 10.1145/174644.174646

Cryptographic limitations on learning Boolean formulae and finite automata
Michael Kearns, Leslie Valiant
Pages: 67-95
DOI: 10.1145/174644.174647
In this paper, we prove the intractability of learning several classes of Boolean functions in the distribution-free model (also called the Probably Approximately Correct or PAC model) of learning from examples. These results are...

Instance complexity
Pekka Orponen, Ker-i Ko, Uwe Schöning, Osamu Watanabe
Pages: 96-121
DOI: 10.1145/174644.174648

Bounds on the time to reach agreement in the presence of timing uncertainty
Hagit Attiya, Cynthia Dwork, Nancy Lynch, Larry Stockmeyer
Pages: 122-152
DOI: 10.1145/174644.174649

Approximation algorithms for NP-complete problems on planar graphs
Brenda S. Baker
Pages: 153-180
DOI: 10.1145/174644.174650

A really temporal logic
Rajeev Alur, Thomas A. Henzinger
Pages: 181-203
DOI: 10.1145/174644.174651
We introduce a temporal logic for the specification of real-time systems. Our logic, TPTL, employs a novel quantifier construct for referencing time: the freeze quantifier binds a variable to the time of the local temporal...