Recognizing well-parenthesized expressions in the streaming model
Frédéric Magniez, Claire Mathieu, Ashwin Nayak · 2010
Motivated by a concrete problem and with the goal of understanding the relationship between the complexity of streaming algorithms and the computational complexity of formal languages, we investigate the problem Dyck(s) of checking matching parentheses, with s different types of parenthesis.