ACM DL

Journal of the ACM (JACM)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of the ACM (JACM), Volume 49 Issue 6, November 2002

Update: Time to publication statistics
Joe Halpern
Pages: 715-715
DOI: 10.1145/602220.602221

Query evaluation via tree-decompositions
Jörg Flum, Markus Frick, Martin Grohe
Pages: 716-752
DOI: 10.1145/602220.602222
A number of efficient methods for evaluating first-order and monadic-second order queries on finite relational structures are based on tree-decompositions of structures or queries. We systematically study these methods.In the first part of the...

Cosmological lower bound on the circuit complexity of a small problem in logic
Larry Stockmeyer, Albert R. Meyer
Pages: 753-784
DOI: 10.1145/602220.602223
An exponential lower bound on the circuit complexity of deciding the weak monadic second-order theory of one successor (WS1S) is proved. Circuits are built from binary operations, or 2-input gates, which compute arbitrary Boolean functions. In...

Correctness properties in a shared-memory parallel language
Gilbert Caplain
Pages: 785-827
DOI: 10.1145/602220.602224
We study a property of correctness of programs written in a shared-memory parallel language. This property is a semantic equivalence between the parallel program and its sequential version, that we define. We consider some standard...

Towards a theory of cache-efficient algorithms
Sandeep Sen, Siddhartha Chatterjee, Neeraj Dumir
Pages: 828-858
DOI: 10.1145/602220.602225
We present a model that enables us to analyze the running time of an algorithm on a computer with a memory hierarchy with limited associativity, in terms of various cache parameters. Our cache model, an extension of Aggarwal and Vitter's I/O model,...