Improved bounds for testing Dyck languages

MaRDI QIDQ4607989zbMATH OpenFDO

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, http://dl.acm.org/citation.cfm?id=3175405

Mathematics Subject Classification ID

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

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

Cited in

(5)

• Streaming algorithms for recognizing nearly well-parenthesized expressions
• 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

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)