Dynamic algorithms for the Dyck languages

DOI10.1007/3-540-60220-8_54MaRDI QIDQ5057425zbMATH OpenOpenAlexFDO

Authors Thore Husfeldt, Peter Bro Miltersen, Theis Rauhe, Søren Skyum, Gudmund S. Frandsen

Publication date 16 December 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60220-8_54

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45) Randomized algorithms (68W20)

Recommendations

• scientific article; zbMATH DE number 572073
• Improved bounds for testing Dyck languages
• A note on multidimensional Dyck languages
• The dynamic complexity of formal languages
• The dynamic complexity of formal languages
• Lexicographical Generation of a Generalized Dyck Language
• scientific article; zbMATH DE number 1003260
• Fast enumeration of words generated by Dyck grammars
• An algorithm for the decomposition of finite languages

Cites work

• Dyn-FO: A parallel, dynamic complexity class
• Dynamic word problems
• Efficient randomized pattern-matching algorithms
• scientific article; zbMATH DE number 140457 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 1003252 (Why is no real title available?)
• scientific article; zbMATH DE number 3224578 (Why is no real title available?)
• Language recognition by marking automata
• Lower bounds for union-split-find related problems on random access machines
• The Complexity of Maintaining an Array and Computing Its Partial Sums
• The design of dynamic data structures
• Word Problems Solvable in Logspace

Cited in

(11)

• Dynamic nested brackets
• Work-sensitive dynamic complexity of formal languages
• Fast enumeration of words generated by Dyck grammars
• Streaming algorithms for recognizing nearly well-parenthesized expressions
• Improved bounds for testing Dyck languages
• Lexicographical Generation of a Generalized Dyck Language
• Lower bounds for dynamic transitive closure, planar point location, and parentheses matching
• On the average complexity of the membership problem for a generalized Dyck language
• An improved algorithm for the \(k\)-Dyck edit distance problem
• Regular languages in the sliding window model
• Dynamic membership for regular tree languages

This page was built for publication: Dynamic algorithms for the Dyck languages

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