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

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

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

• 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?)
• Dyn-FO: A parallel, dynamic complexity class
• Dynamic word problems
• Efficient randomized pattern-matching algorithms
• 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

(10)

• An improved algorithm for the \(k\)-Dyck edit distance problem
• Dynamic nested brackets
• Regular languages in the sliding window model
• Fast enumeration of words generated by Dyck grammars
• Work-sensitive dynamic complexity of formal languages
• Improved bounds for testing Dyck languages
• 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
• Lexicographical Generation of a Generalized Dyck Language
• Streaming algorithms for recognizing nearly well-parenthesized expressions

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)