Optimal Prediction for Prefetching in the Worst Case
- 1 December 1998
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 27 (6), 1617-1636
- https://doi.org/10.1137/s0097539794261817
Abstract
We study the learnability of read-k-satisfy-j (RkSj) DNF formulas. These are boolean formulas in disjunctive normal form (DNF), in which the maximum number of occurrences of a variable is bounded by k, and the number of terms satisfied ...Keywords
This publication has 17 references indexed in Scilit:
- Elements of Information TheoryPublished by Wiley ,2001
- Competitive Paging with Locality of ReferenceJournal of Computer and System Sciences, 1995
- Large deviations for coding Markov chains and Gibbs random fieldsIEEE Transactions on Information Theory, 1993
- Analysis of arithmetic coding for data compressionInformation Processing & Management, 1992
- Universal prediction of individual sequencesIEEE Transactions on Information Theory, 1992
- Competitive paging algorithmsJournal of Algorithms, 1991
- Working Sets Past and PresentIEEE Transactions on Software Engineering, 1980
- Compound Bayes Predictors for Sequences with Apparent Markov StructureIEEE Transactions on Systems, Man, and Cybernetics, 1977
- A study of replacement algorithms for a virtual-storage computerIBM Systems Journal, 1966
- An analog of the minimax theorem for vector payoffsPacific Journal of Mathematics, 1956