Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 45 Issue 4, July 1998

Formal verification of complex coherence protocols using symbolic state models
Fong Pong, Michel Dubois
Pages: 557-587
DOI: 10.1145/285055.285057
Directory-based coherence protocols in shared-memory multiprocessors are so complex that verification techniques based on automated procedures are required to establish their correctness. State enumeration approaches are well-suited to the...

On the decidability and axiomatization of query finiteness in deductive databases
Michael Kifer
Pages: 588-633
DOI: 10.1145/285055.285058
A database query is finite if its result consists of a finite sets tuples. For queries formulated as sets of pure Horn rules, the problem of determining finiteness is, in general, undecidable.In this paper, we...

A threshold of ln n for approximating set cover
Uriel Feige
Pages: 634-652
DOI: 10.1145/285055.285059
Given a collection F of subsets of S = {1,…,n}, set cover is the problem of...

Property testing and its connection to learning and approximation
Oded Goldreich, Shari Goldwasser, Dana Ron
Pages: 653-750
DOI: 10.1145/285055.285060
In this paper, we consider the question of determining whether a function f has property P or is &egr;-far from any function with property P. A property testing algorithm is given a sample of the value of...