Search ACM DL

Search Issue

enter search term and/or author name

**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 − 2^{−k} +*p* 2^{−k} of its clauses (note that every *k*-CNF...