Testing membership in formal languages implicitly represented by boolean functions
Combinatorial property testing, initiated formally by Goldreich, Goldwasser, and Ron in [Goldreich et al. (1998)] and inspired by Rubinfeld and Sudan in [ Rubinfeld and Sudan 1996], deals with the relaxation of decision problems. Given a property P the aim is to decide whether a given input satisfies the property P or is far from having the property. A property P can be described as a language, i.e., a nonempty family of binary words. The associated property to a family of boolean functions f = (f(n)) is the set of 1-inputs of f. By an attempt to correlate the notion of testing to other notions of low complexity property testing has been considered in the context of formal languages. Here, a brief summary of results on testing properties defined by formal languages and by languages implicitly represented by small restricted branching programs is provided.
formal languages boolean functions property testing binary decision diagrams (bdds) branching programs (bps) computational complexity randomness sublinear algorithms