Testing Membership in Formal Languages Implicitly Represented by Boolean Functions

Простая страница элемента
dc.creatorBollig,Beate
dc.date2006
dc.date.accessioned2024-02-06T12:54:25Z
dc.date.available2024-02-06T12:54:25Z
dc.descriptionCombinatorial 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.
dc.formattext/html
dc.identifierhttps://doi.org/10.3217/jucs-012-06-0710
dc.identifierhttps://lib.jucs.org/article/28627/
dc.identifier.urihttps://openrepository.mephi.ru/handle/123456789/9040
dc.languageen
dc.publisherJournal of Universal Computer Science
dc.relationinfo:eu-repo/semantics/altIdentifier/eissn/0948-6968
dc.relationinfo:eu-repo/semantics/altIdentifier/pissn/0948-695X
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rightsJ.UCS License
dc.sourceJUCS - Journal of Universal Computer Science 12(6): 710-724
dc.subjectbinary decision diagrams (BDDs)
dc.subjectboolean functions
dc.subjectbranching programs (BPs)
dc.subjectcomputational complexity
dc.subjectformal languages
dc.subjectproperty testing
dc.subjectrandomness
dc.subjectsublinear algorithms
dc.titleTesting Membership in Formal Languages Implicitly Represented by Boolean Functions
dc.typeResearch Article
Файлы
Коллекции
Публикации в журналах НИЯУ МИФИ