Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 40 Issue 4, Sept. 1993

Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs
Edith Cohen, Nimrod Megiddo
Pages: 791-830
DOI: 10.1145/153724.153727

On the analytical modeling of database concurrency control
Philip S. Yu, Daniel M. Dias, Stephen S. Lavenberg
Pages: 831-872
DOI: 10.1145/153724.153733
The Concurrency Control (CC) scheme employed can profoundly affect the performance of transaction-processing systems. In this paper, a simple unified approximate analysis methodology to model the effect on system performance of data contention...

Atomic snapshots of shared memory
Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, Nir Shavit
Pages: 873-890
DOI: 10.1145/153724.153741
This paper introduces a general formulation of atomic snapshot memory, a shared memory partitioned into words written (updated) by individual processes, or instantaneously...

The parallel complexity of simple logic programs
Foto Afrati, Christos H. Papadimitriou
Pages: 891-916
DOI: 10.1145/153724.153752
We consider logic programs with a single recursive rules, whose right-hand side consists of binary relations forming a chain. We give a complete characterization of all programs of this form that are computable in NC (assuming that...

Knowledge, probability, and adversaries
Joseph Y. Halpern, Mark R. Tuttle
Pages: 917-960
DOI: 10.1145/153724.153770
What should it mean for an agent to know or believe an assertion is true with probability 9.99? Different papers [2, 6, 15] give different answers, choosing to use quite different probability spaces when computing the probability that an agent...

Modal nonmonotonic logics: ranges, characterization, computation
V. Wiktor Marek, Grigori F. Schwarz, Mirosław Truszczyński
Pages: 961-988
DOI: 10.1145/153724.153773
Many nonmonotonic formalism, including default logic, logic programming with stable models, and autoepistemic logic, can be represented faithfully by means of modal nonmonotonic logics in the family proposed by McDermott and Doyle. In this paper...