enter search term and/or author name
Deciding equivalences among conjunctive aggregate queries
Sara Cohen, Werner Nutt, Yehoshua Sagiv
Article No.: 5
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
We solve an open question of Milner . 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...
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...
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
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,...
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...