Testing Membership in Languages that Have Small Width Branching Programs

DOI10.1137/S009753970038211XMaRDI QIDQ3149882zbMATH OpenFDO

Authors Ilan Newman

Publication date 29 September 2002

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

randomized algorithmsproperty testingbranching programs

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Fundamentals of Computation Theory
• Testing Computability by Width Two OBDDs
• Regular languages are testable with a constant number of queries
• scientific article; zbMATH DE number 2019622
• Functions that have read‐twice constant width branching programs are not necessarily testable

Cited in

(20)

• Property testing of massively parametrized problems -- a survey
• Approximate membership for regular languages modulo the edit distance
• Testing convexity properties of tree colorings
• Testing membership in parenthesis languages
• Proofs of proximity for context-free languages and read-once branching programs
• scientific article; zbMATH DE number 2019622 (Why is no real title available?)
• Fundamentals of Computation Theory
• Second-order finite automata
• Functions that have read‐twice constant width branching programs are not necessarily testable
• Proofs of proximity for context-free languages and read-once branching programs
• \(\omega\)-regular languages are testable with a constant number of queries
• Functions that have read-once branching programs of quadratic size are not necessarily testable
• Testing membership in counter automaton languages
• A combinatorial characterization of smooth LTCs and applications
• A large lower bound on the query complexity of a simple Boolean function
• On the minimization of (complete) ordered binary decision diagrams
• Distribution-free connectivity testing for sparse graphs
• On the Query Complexity of Testing Orientations for Being Eulerian
• Testing computability by width-two OBDDs
• Testing of matrix-poset properties

This page was built for publication: Testing Membership in Languages that Have Small Width Branching Programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3149882)