Improved bounds for testing Dyck languages

zbMATH Open1403.68111arXiv1707.06606MaRDI QIDQ4607989FDOQ4607989

Authors: Eldar Fischer, Frédéric Magniez, Tatiana Starikovskaya 

Publication date: 15 March 2018

Full work available at URL: https://arxiv.org/abs/1707.06606

Recommendations

• scientific article; zbMATH DE number 1833419
• Testing membership in parenthesis languages
• Recognizing well-parenthesized expressions in the streaming model
• Dynamic algorithms for the Dyck languages
• Regular languages are testable with a constant number of queries

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Randomized algorithms (68W20)

Cited In (5)

• An improved algorithm for the \(k\)-Dyck edit distance problem
• Recognizing well-parenthesized expressions in the streaming model
• On the average complexity of the membership problem for a generalized Dyck language
• Dynamic algorithms for the Dyck languages
• Streaming algorithms for recognizing nearly well-parenthesized expressions

This page was built for publication: Improved bounds for testing Dyck languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607989)