Testing Membership in Languages that Have Small Width Branching Programs
From MaRDI portal
Publication:3149882
DOI10.1137/S009753970038211XzbMath1051.68069MaRDI QIDQ3149882
Publication date: 29 September 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items (14)
Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs ⋮ Proofs of proximity for context-free languages and read-once branching programs ⋮ Second-order finite automata ⋮ Approximate membership for regular languages modulo the edit distance ⋮ Distribution-free connectivity testing for sparse graphs ⋮ On the Query Complexity of Testing Orientations for Being Eulerian ⋮ Testing of matrix-poset properties ⋮ On the minimization of (complete) ordered binary decision diagrams ⋮ Testing convexity properties of tree colorings ⋮ Property Testing of Massively Parametrized Problems – A Survey ⋮ Functions that have read-once branching programs of quadratic size are not necessarily testable ⋮ A combinatorial characterization of smooth LTCs and applications ⋮ Testing computability by width-two OBDDs ⋮ A large lower bound on the query complexity of a simple Boolean function
This page was built for publication: Testing Membership in Languages that Have Small Width Branching Programs
