Streaming algorithms for recognizing nearly well-parenthesized expressions

Andreas Krebs, Nutan Limaye, Srikanth Srinivasan

We study the streaming complexity of the membership problem of 1-turn-Dyck2 and Dyck2 when there are a few errors in the input string. 1-turn-Dyck2 with errors: We prove that there…