Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 54 Issue 2, April 2007

Deciding equivalences among conjunctive aggregate queries
Sara Cohen, Werner Nutt, Yehoshua Sagiv
Article No.: 5
DOI: 10.1145/1219092.1219093

Equivalence of aggregate queries is investigated for the class of conjunctive queries with comparisons and the aggregate operators count, count-distinct, min, max, and sum. Essentially, this class contains unnested SQL queries with the above...

A characterization of regular expressions under bisimulation
J. C. M. Baeten, F. Corradini, C. A. Grabmayer
Article No.: 6
DOI: 10.1145/1219092.1219094

We solve an open question of Milner [1984]. We define a set of so-called well-behaved finite automata that, modulo bisimulation equivalence, corresponds exactly to the set of regular expressions, and we show how to determine whether a given finite...

The rational numbers as an abstract data type
J. A. Bergstra, J. V. Tucker
Article No.: 7
DOI: 10.1145/1219092.1219095

We give an equational specification of the field operations on the rational numbers under initial algebra semantics using just total field operations and 12 equations. A consequence of this specification is that 0−1 = 0, an...

The measurement calculus
Vincent Danos, Elham Kashefi, Prakash Panangaden
Article No.: 8
DOI: 10.1145/1219092.1219096

Measurement-based quantum computation has emerged from the physics community as a new approach to quantum computation where the notion of measurement is the main driving force of computation. This is in contrast with the more traditional circuit...

Fast computation of low-rank matrix approximations
Dimitris Achlioptas, Frank Mcsherry
Article No.: 9
DOI: 10.1145/1219092.1219097

Given a matrix A, it is often desirable to find a good approximation to A that has low rank. We introduce a simple technique for accelerating the computation of such approximations when A has strong spectral features, that is,...

On the maximum satisfiability of random formulas
Dimitris Achlioptas, Assaf Naor, Yuval Peres
Article No.: 10
DOI: 10.1145/1219092.1219098

Say that a k-CNF a formula is p-satisfiable if there exists a truth assignment satisfying a fraction 1 − 2k +p 2k of its clauses (note that every k-CNF...