Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 43 Issue 5, Sept. 1996

Optimal prefetching via data compression
Jeffrey Scott Vitter, P. Krishnan
Pages: 771-793
DOI: 10.1145/234752.234753
Caching and prefetching are important mechanisms for speeding up access time to data on secondary storage. Recent work in competitive online algorithms has uncovered several promising new algorithms for caching. In this paper, we apply a form of...

A combinatorial treatment of balancing networks
Costas Busch, Marios Mavronicolas
Pages: 794-839
DOI: 10.1145/234752.234754
Balancing networks, originally introduced by Aspnes et al. (Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pp. 348-358, May 1991), represent a new class of distributed, low-contention data...

How many queries are needed to learn?
Lisa Hellerstein, Krishnan Pillaipakkamnatt, Vijay Raghavan, Dawn Wilkins
Pages: 840-862
DOI: 10.1145/234752.234755
We investigate the query complexity of exact learning in the membership and (proper) equivalence query model. We give a complete characterization of concept classes that are learnable with a polynomial number of polynomial sized queries in this...

The meaning of negative premises in transition system specifications
Roland Bol, Jan Friso Groote
Pages: 863-914
DOI: 10.1145/234752.234756
We present a general theory for the use of negative premises in the rules of Transition System Specifications (TSSs). We formulate a criterion that should be satisfied by a TSS in order to be meaningful, that is, to unequivocally define a...