Property Testing of Massively Parametrized problems -- A survey <s> Testing membership in read-once branching programs: <s> We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron (1996). The subject of this paper is testing regular languages. Our main result is as follows. For a regular language L/spl isin/{0, 1}* and an integer n there exists a randomized algorithm which always accepts a word w of length n if w/spl isin/L, and rejects it with high probability if w has to be modified in at least En positions to create a word in L. The algorithm queries O~(1//spl epsiv/) bits of w. This query complexity is shown to be optimal up to a factor poly-logarithmic in 1//spl epsiv/. We also discuss testability of more complex languages and show, in particular, that the query complexity required for testing context free languages cannot be bounded by any function of /spl epsiv/. The problem of testing regular languages can be viewed as a part of a very general approach, seeking to probe testability of properties defined by logical means. <s> BIB001 </s> Property Testing of Massively Parametrized problems -- A survey <s> Testing membership in read-once branching programs: <s> Combinatorial property testing, initiated formally by Goldreich, Goldwasser, and Ron in [J. ACM, 45 (1998), pp. 653--750] and inspired by Rubinfeld and Sudan [SIAM J. Comput., 25 (1996), pp. 252--271], deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x has the property or is "far" from having the property. ::: The main result here is that, if ${\cal G}= \{ g_n:\{0,1\}^n \rightarrow \{0,1\} \}$ is a family of Boolean functions which have oblivious read-once branching programs of width w, then, for every n and $\epsilon > 0$, there is a randomized algorithm that always accepts every $x \in \{0,1\}^n$ if $g_n(x)=1$ and rejects it with high probability if at least $\epsilon n$ bits of $x$ should be modified in order for it to be in gn-1(1). The algorithm makes $(\frac{2^{w}}{\epsilon})^{O(w)}$ queries. In particular, for constant $\epsilon$ and w, the query complexity is O(1). ::: This generalizes the results of Alon et al.\ [Proceedings of the40th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, 1999, pp. 645--655] asserting that regular languages are $\epsilon$-testable for every $\epsilon > 0$. <s> BIB002
In BIB002 the following problem is considered: Given a read-once deterministic oblivious branching program P on n Boolean variables 1 , the set of inputs is the set of all Boolean assignments to the variables. It is proved in BIB002 that the satisfiability (or membership) problem can be tested (nonadaptively, 1-sided error test) using O(exp(2 w / )) queries. The preprocessing is rather heavy, but can be done in time poly(n). We note that this result is a generalization of a result of BIB001 stating that testing membership in regular languages is testable. The result of BIB001 can already be viewed as fits the massively-parametrized framework. There however, the preprocessing is 'light' as the same fixed (hence constant size) automaton serves as the defining mechanism for every input length word.