Aarhus University Seal / Aarhus Universitets segl

Dynamic algorithms for the Dyck languages

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science
We study Dynamic Membership problems for the Dyck languages, the class of strings of properly balanced parentheses. We also study the Dynamic Word problem for the free group. We present deterministic algorithms and data structures which maintain a string under replacements of symbols, insertions, and deletions of symbols, and language membership queries. Updates and queries are handled in polylogarithmic 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.
Original languageEnglish
Title of host publicationAlgorithms and Data Structures : 4th International Workshop, WADS '95 Kingston, Canada, August 16-18, 1995 Proceedings
EditorsSelim G. Akl, Frank Dehne, Jörg-Rüdiger Sack, Nicola Santoro
Number of pages10
PublisherSpringer
Publication year1995
Pages98-108
DOIs
Publication statusPublished - 1995
EventWorkshop on Algorithmsand Data Structures - Kingston, Canada
Duration: 16 Aug 199518 Aug 1995
Conference number: 4

Conference

ConferenceWorkshop on Algorithmsand Data Structures
Nummer4
LandCanada
ByKingston
Periode16/08/199518/08/1995

See relations at Aarhus University Citationformats

ID: 21682351