Testing Membership in Formal Languages Implicitly Represented by Boolean Functions

Beate Bollig (University Dortmund, Germany)

Abstract: 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.

Keywords: binary decision diagrams (BDDs), boolean functions, branching programs (BPs), computational complexity, formal languages, property testing, randomness, sublinear algorithms

Categories: F.1.3, F.2.2, G.3