enter search term and/or author name
Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra
Andrei Krokhin, Peter Jeavons, Peter Jonsson
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
We consider the traveling salesman problem when the cities are points in &#x211D;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
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
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
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...