We present a new model-based approach for testing systems that use sequences of actions and assertions as test vectors. Our solution includes a method for quantifying testing quality, a tool for generating high-quality test suites based on the coverage criteria we propose, and a framework for assessing risks. For testing quality, we propose a method that specifies generalized coverage criteria over sequences of actions, which extends previous approaches. Our publicly available tool demonstrates how to extract effective test suites from test plans based on these criteria. We also present a Bayesian approach for measuring the probabilities of bugs or risks, and show how this quantification can help achieve an informed balance between exploitation and exploration in testing. Finally, we provide an empirical evaluation demonstrating the effectiveness of our tool in finding bugs, assessing risks, and achieving coverage.

We introduce ω^ ̅-NED, an edit distance between infinite words, that is a natural extension of NED, the normalized edit distance between finite words. We show it is a metric on (equivalence classes of) infinite words. We provide a polynomial time algorithm to compute the distance between two ultimately periodic words, and a polynomial time algorithm to compute the distance between two regular ω-languages given by non-deterministic Büchi automata.

We study the problem of accurately estimating the data reduction ratio achieved by deduplication and compression on a specific data set. This turns out to be a challenging task - It has been shown both empirically and analytically that essentially all of the data at hand needs to be inspected in order to come up with a accurate estimation when deduplication is involved. Moreover, even when permitted to inspect all the data, there are challenges in devising an efficient, yet accurate, method. Efficiency in this case refers to the demanding CPU, memory and disk usage associated with deduplication and compression. Our study focuses on what can be done when scanning the entire data set. We present a novel two-phased framework for such estimations. Our techniques are provably accurate, yet run with very low memory requirements and avoid overheads associated with maintaining large deduplication tables. We give formal proofs of the correctness of our algorithm, compare it to existing techniques from the database and streaming literature and evaluate our technique on a number of real world workloads. For example, we estimate the data reduction ratio of a 7 TB data set with accuracy guarantees of at most a 1% relative error while using as little as 1 MB of RAM (and no additional disk access). In the interesting case of full-file deduplication, our framework readily accepts optimizations that allow estimation on a large data set without reading most of the actual data. For one of the workloads we used in this work we achieved accuracy guarantee of 2% relative error while reading only 27% of the data from disk. Our technique is practical, simple to implement, and useful for multiple scenarios, including estimating the number of disks to buy, choosing a deduplication technique, deciding whether to dedupe or not dedupe and conducting large-scale academic studies related to deduplication ratios.

The authors have solved the all pairs shortest distances (APSD) problem for graphs with integer edge lengths. Our algorithm is subcubic for edge lengths of small (⩽M) absolute value. In this paper we show how to transform these algorithms to solve the all pairs shortest paths (APSP), in the same time complexity, up to a polylogarithmic factor. Forn=|V| the number of vertices,Mthe bound on edge length, andωthe exponent of matrix multiplication, we get the following results: 1. A directed nonnegative APSP(n, M) algorithm which runs inÕ(T(n, M)) time, where T(n, m)=\big\{\begin{align}M^{\omega -1)/2} n^{3+\omega )/2}, & 1\le M\le n^{3-\omega )/(\omega +1)}\\ Mn^{5\omega -3)/(\omega +1)}, & n^{(3-\omega )/(\omega +1)}\le M\le n^2(3-\omega )/(\omega +1)}.\end{align} 2. An undirected APSP(n, M) algorithm which runs inÕ(M(ω+1)/2nω log(Mn)) time. 3. A general APSP(n, M) algorithm which runs inÕ((Mn)(3+ω)/2).

The subcubic (O(n/sup w/) for w(3) algorithms to multiply Boolean matrices do not provide the witnesses; namely, they compute C=A.B but if C/sub ij/=1 they do not find an index k (a witness) such that A/sub ik/=B/sub kj/=1. The authors design a deterministic algorithm for computing the matrix of witnesses that runs in O(n/sup w/) time, where here O(n/sup w/) denotes O(n/sup w/(log n)/sup O(1)/). The subcubic methods to compute the shortest distances between all pairs of vertices also do not provide for witnesses; namely they compute the shortest distances but do not generate information for computing quickly the paths themselves. A witness for a shortest path from v/sub i/ to v/sub j/ is an index k such that v/sub k/ is the first vertex on such a path. They describe subcubic methods to compute such witnesses for several versions of the all pairs shortest paths problem. As a result, they derive shortest paths algorithms that provide characterization of the shortest paths in addition to the shortest distances in the same time (up to a polylogarithmic factor) needed for computing the distances; namely O(n/sup (3+w)/2/) time in the directed case and O(n/sup w/) time in the undirected case. They also design an algorithm that computes witnesses for the transitive closure in the same time needed to compute witnesses for Boolean matrix multiplication.>

This paper describes a new approach for solving the subset-sum problem. It is useful for solving other NP-hard problems. The limits and potential of this approach are discussed. The approach yields an algorithm for solving the dense version of the subset-sum problem. It runs in time $O(\ell \log \ell )$, where $\ell $ is the bound on the size of the elements. But for dense enough inputs and target numbers near the middle sum, it runs in time $O(m)$, where m is the number of elements. Consequently, it improves the previously best algorithms by at least one order of magnitude and sometimes by two. The algorithm yields a characterization of the set of subset sums as a collection of arithmetic progressions with the same difference. This characterization is derived by elementary number-theoretic and algorithmic techniques. Such a characterization was first obtained by using analytic number theory and yielded inferior algorithms.