Dynamic algorithms for the Dyck languages
From MaRDI portal
Publication:5057425
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
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