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 aproperty p the aim is to decide whether a given input satisfies the property p or is farfrom having the property. a property p can be described as a language, i.e., a nonemptyfamily of binary words. the associated property to a family of boolean functionsf = (fn) is the set of 1-inputs of f. by an attempt to correlate the notion of testingto other notions of low complexity property testing has been considered in the contextof formal languages. here, a brief summary of results on testing properties defined byformal languages and by languages implicitly represented by small restricted branchingprograms is provided.