Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 48 Issue 6, November 2001

Monotonic reductions, representative equivalence, and compilation of intractable problems
Paolo Liberatore
Pages: 1091-1125
DOI: 10.1145/504794.504795
The idea of preprocessing part of the input of a problem in order to improve efficiency has been employed by several researchers in several areas of computer science. In this article, we show sufficient conditions to prove that an intractable problem...

A Laplace transform algorithm for the volume of a convex polytope
Jean B. Lasserre, Eduardo S. Zeron
Pages: 1126-1140
DOI: 10.1145/504794.504796
We provide two algorithms for computing the volume of the convex polytope Ω : = {x ∈ ℝn+ | Axb}, for A, ∈ ℝm×n, b...

Managing periodically updated data in relational databases: a stochastic modeling approach
Avigdor Gal, Jonathan Eckstein
Pages: 1141-1183
DOI: 10.1145/504794.504797
Recent trends in information management involve the periodic transcription of data onto secondary devices in a networked environment, and the proper scheduling of these transcriptions is critical for efficient data management. To assist in the...

Deciding first-order properties of locally tree-decomposable structures
Markus Frick, Martin Grohe
Pages: 1184-1206
DOI: 10.1145/504794.504798
We introduce the concept of a class of graphs, or more generally, relational structures, being locally tree-decomposable. There are numerous examples of locally tree-decomposable classes, among them the class of planar graphs and all classes...

Register-machine based processes
Jan A. Bergstra, Alban Ponse
Pages: 1207-1241
DOI: 10.1145/504794.504799
We study extensions of the process algebra axiom system ACP with two recursive operations: the binary Kleene star *, which is defined by x*y = x(x*y + y, and the...