Testing membership in parenthesis languages

DOI10.1002/RSA.10067MaRDI QIDQ4798183zbMATH OpenOpenAlexFDO

Authors Michal Parnas, Dana Ron, Ronitt Rubinfeld

Publication date 19 March 2003

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.10067

zbMATH Keywords

Dyck languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 1833419
• Testing Membership in Languages that Have Small Width Branching Programs
• Testing membership in counter automaton languages
• scientific article; zbMATH DE number 2043550
• Testing membership for timed automata
• Testing for class membership in multi-parent hierarchies
• Exact and approximate membership testers
• scientific article; zbMATH DE number 1507233
• Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata

Cited in

(10)

• Quantum algorithm for Dyck language with multiple types of brackets
• Syntax checking either way
• Hierarchy theorems for property testing
• Improved bounds for testing Dyck languages
• Truly subcubic algorithms for language edit distance and RNA folding via fast bounded-difference min-plus product
• scientific article; zbMATH DE number 1833419 (Why is no real title available?)
• Hierarchy theorems for property testing
• Quantum property testing algorithm for the concatenation of two palindromes language
• Property testing of regular languages with applications to streaming property testing of visibly pushdown languages
• Distribution-free connectivity testing for sparse graphs

This page was built for publication: Testing membership in parenthesis languages

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