Dynamic algorithms for the Dyck languages

DOI10.1007/3-540-60220-8_54zbMath1502.68163OpenAlexW2170921807MaRDI QIDQ5057425

Thore Husfeldt, Søren Skyum, Theis Rauhe, Peter Bro Miltersen, Gudmund Skovbjerg 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) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Randomized algorithms (68W20)

Related Items

Dynamic nested brackets, Lower bounds for dynamic transitive closure, planar point location, and parentheses matching, Work-sensitive dynamic complexity of formal languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The design of dynamic data structures
• Dyn-FO: A parallel, dynamic complexity class
• Lower bounds for union-split-find related problems on random access machines
• Efficient randomized pattern-matching algorithms
• The Complexity of Maintaining an Array and Computing Its Partial Sums
• Word Problems Solvable in Logspace
• Dynamic word problems
• Language recognition by marking automata