Testing Membership in Languages that Have Small Width Branching Programs
From MaRDI portal
Publication:3149882
DOI10.1137/S009753970038211XzbMATH Open1051.68069MaRDI QIDQ3149882FDOQ3149882
Authors: Ilan Newman 
Publication date: 29 September 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Recommendations
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cited In (20)
- 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
- Title not available (Why is that?)
- Fundamentals of Computation Theory
- Functions that have read‐twice constant width branching programs are not necessarily testable
- Second-order finite automata
- 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 of matrix-poset properties
- Testing computability by width-two OBDDs
- Property testing of massively parametrized problems -- a survey
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)
