Dynamic algorithms for the Dyck languages

Gudmund Skovbjerg Frandsen; Thore Husfeldt; Peter Bro Miltersen; Theis Rauhe; Søren Skyum

doi:10.1007/3-540-60220-8_54

Dynamic algorithms for the Dyck languages

Gudmund Skovbjerg Frandsen, Thore Husfeldt, Peter Bro Miltersen, Theis Rauhe, Søren Skyum

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

Abstract

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.

Originalsprog	Engelsk
Titel	Algorithms and Data Structures : 4th International Workshop, WADS '95 Kingston, Canada, August 16-18, 1995 Proceedings
Redaktører	Selim G. Akl, Frank Dehne, Jörg-Rüdiger Sack, Nicola Santoro
Antal sider	10
Forlag	Springer
Publikationsdato	1995
Sider	98-108
DOI	https://doi.org/10.1007/3-540-60220-8_54
Status	Udgivet - 1995
Begivenhed	Workshop on Algorithmsand Data Structures - Kingston, Canada Varighed: 16 aug. 1995 → 18 aug. 1995 Konferencens nummer: 4

Konference

Konference	Workshop on Algorithmsand Data Structures
Nummer	4
Land/Område	Canada
By	Kingston
Periode	16/08/1995 → 18/08/1995

Adgang til dokumentet

10.1007/3-540-60220-8_54

Citationsformater

@inproceedings{2b650670b04411df8c1a000ea68e967b,

title = "Dynamic algorithms for the Dyck languages",

abstract = "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.",

author = "Frandsen, {Gudmund Skovbjerg} and Thore Husfeldt and Miltersen, {Peter Bro} and Theis Rauhe and S{\o}ren Skyum",

year = "1995",

doi = "10.1007/3-540-60220-8_54",

language = "English",

pages = "98--108",

editor = "Akl, {Selim G.} and Frank Dehne and J{\"o}rg-R{\"u}diger Sack and Nicola Santoro",

booktitle = "Algorithms and Data Structures",

publisher = "Springer",

address = "Netherlands",

note = "Workshop on Algorithmsand Data Structures ; Conference date: 16-08-1995 Through 18-08-1995",

}

Frandsen, GS, Husfeldt, T, Miltersen, PB, Rauhe, T & Skyum, S 1995, Dynamic algorithms for the Dyck languages. i SG Akl, F Dehne, J-R Sack & N Santoro (red), Algorithms and Data Structures: 4th International Workshop, WADS '95 Kingston, Canada, August 16-18, 1995 Proceedings. Springer, s. 98-108, Workshop on Algorithmsand Data Structures, Kingston, Canada, 16/08/1995. https://doi.org/10.1007/3-540-60220-8_54

Dynamic algorithms for the Dyck languages. / Frandsen, Gudmund Skovbjerg; Husfeldt, Thore; Miltersen, Peter Bro et al.
Algorithms and Data Structures: 4th International Workshop, WADS '95 Kingston, Canada, August 16-18, 1995 Proceedings. red. / Selim G. Akl; Frank Dehne; Jörg-Rüdiger Sack; Nicola Santoro. Springer, 1995. s. 98-108.

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - Dynamic algorithms for the Dyck languages

AU - Frandsen, Gudmund Skovbjerg

AU - Husfeldt, Thore

AU - Miltersen, Peter Bro

AU - Rauhe, Theis

AU - Skyum, Søren

N1 - Conference code: 4

PY - 1995

Y1 - 1995

N2 - 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.

AB - 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.

U2 - 10.1007/3-540-60220-8_54

DO - 10.1007/3-540-60220-8_54

M3 - Article in proceedings

SP - 98

EP - 108

BT - Algorithms and Data Structures

A2 - Akl, Selim G.

A2 - Dehne, Frank

A2 - Sack, Jörg-Rüdiger

A2 - Santoro, Nicola

PB - Springer

T2 - Workshop on Algorithmsand Data Structures

Y2 - 16 August 1995 through 18 August 1995

ER -

Dynamic algorithms for the Dyck languages

Abstract

Konference

Adgang til dokumentet

Fingeraftryk

Citationsformater