Paper Info
Title
Dynamic Algorithms for the Dyck Languages
Abstract
We study Dynamic Membership problems for the Dyck lan- guages, the class of strings of properly balanced parentheses. We also study the Dynamic Word problem for the free group. We present de- terministic algorithms and data structures which maintain a string un- der replacements of symbols, insertions, and deletions of symbols, and language membership queries. Updates and queries are handled in poly- logarithmic time. We also give both Las Vegas- and Monte Carlo-type randomised algorithms to achieve better running times, and present lower bounds on the complexity for variants of the problems.
Year
DOI
Venue
1995
10.1007/3-540-60220-8_54
WADS
Keywords
Field
DocType
dyck languages,dynamic algorithms,lower bound,monte carlo,word problem,free group
Data structure,Combinatorics,Word problem (mathematics education),Computer science,Algorithm,Theoretical computer science,Dynamic problem,Dynamic data structures,Free group
Conference
Volume
ISSN
ISBN
955
0302-9743
3-540-60220-8
Citations 
PageRank 
References 
7
0.57
12
Authors
5
Name
Order
Citations
PageRank
Gudmund Skovbjerg Frandsen18010.84
Thore Husfeldt273340.87
Peter Bro Miltersen3114694.49
Theis Rauhe466135.11
Søren Skyum5221.36