JUCS - Journal of Universal Computer Science 12(6): 710-724, doi: 10.3217/jucs-012-06-0710
Testing Membership in Formal Languages Implicitly Represented by Boolean Functions
expand article infoBeate Bollig
‡ University Dortmund, Germany
Open Access
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 = (fn) 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.
binary decision diagrams (BDDs), boolean functions, branching programs (BPs), computational complexity, formal languages, property testing, randomness, sublinear algorithms