Fundamentals of Computation Theory
From MaRDI portal
Publication:5492933
DOI10.1007/11537311zbMATH Open1122.68441OpenAlexW2491671784MaRDI QIDQ5492933FDOQ5492933
Authors: Beate Bollig 
Publication date: 20 October 2006
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/11537311
Recommendations
- A large lower bound on the query complexity of a simple Boolean function
- Testing Membership in Languages that Have Small Width Branching Programs
- Functions that have read‐twice constant width branching programs are not necessarily testable
- Functions that have read-once branching programs of quadratic size are not necessarily testable
- Testing Computability by Width Two OBDDs
Cited In (9)
- Proofs of proximity for context-free languages and read-once branching programs
- 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
- Functions that have read-once branching programs of quadratic size are not necessarily testable
- A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy
- Testing Membership in Languages that Have Small Width Branching Programs
- A large lower bound on the query complexity of a simple Boolean function
- Length of polynomials over finite groups
- Abstract Combinatorial Programs and Efficient Property Testers
This page was built for publication: Fundamentals of Computation Theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5492933)
