Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 50 Issue 5, September 2003

Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra
Andrei Krokhin, Peter Jeavons, Peter Jonsson
Pages: 591-640
DOI: 10.1145/876638.876639
Allen's interval algebra is one of the best established formalisms for temporal reasoning. This article provides the final step in the classification of complexity for satisfiability problems over constraints expressed in this algebra. When the...

The geometric maximum traveling salesman problem
Alexander Barvinok, Sándor P. Fekete, David S. Johnson, Arie Tamir, Gerhard J. Woeginger, Russ Woodroofe
Pages: 641-664
DOI: 10.1145/876638.876640
We consider the traveling salesman problem when the cities are points in ℝd for some fixed d and distances are computed according to geometric distances, determined by some norm. We show that for any polyhedral...

The performance of difference coding for sets and relational tables
Wei Biao Wu, Chinya V. Ravishankar
Pages: 665-693
DOI: 10.1145/876638.876641
We characterize the performance of difference coding for compressing sets and database relations through an analysis of the problem of estimating the number of bits needed for storing the spacings between values in sets of integers. We provide...

Definable relations and first-order query languages over strings
Michael Benedikt, Leonid Libkin, Thomas Schwentick, Luc Segoufin
Pages: 694-751
DOI: 10.1145/876638.876642
We study analogs of classical relational calculus in the context of strings. We start by studying string logics. Taking a classical model-theoretic approach, we fix a set of string operations and look at the resulting collection of definable...

Counterexample-guided abstraction refinement for symbolic model checking
Edmund Clarke, Orna Grumberg, Somesh Jha, Yuan Lu, Helmut Veith
Pages: 752-794
DOI: 10.1145/876638.876643
The state explosion problem remains a major hurdle in applying symbolic model checking to large hardware designs. State space abstraction, having been essential for verifying designs of industrial complexity, is typically a manual process, requiring...