Article ID Journal Published Year Pages File Type
6873771 Information and Computation 2018 27 Pages PDF
Abstract
We construct proofs of proximity for two natural classes of properties: (1) context-free languages, and (2) languages accepted by small read-once branching programs. Our main results are:
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
Proofs of proximity for context-free languages and read-once branching programs
Authors
, , ,