1 paper · 1 filter
Tim Jackman, Diptaksho Palit, Sofya Raskhodnikova
We study the query complexity of testing membership in structured string languages, focusing on Dyck languages and natural generalizations. A tester receives query access to a word…