Advanced

Dynamic nested brackets

Alstrup, S; Husfeldt, Thore LU and Rauhe, T (2004) In Information and Computation 193(2). p.75-83
Abstract
We consider the problem of maintaining a string of n brackets '('or')' under the operation reverse(i) that changes the ith bracket from '('to')' or vice versa, and returns 'yes' if and only if the resulting string is properly balanced. We show that this problem can be solved on the RAM in time O(log n/log log n) per operation using linear space and preprocessing. Moreover, we show that this is optimal in the sense that every data structure supporting reverse (no matter its space and preprocessing complexity) needs time Omega(Iog n/log log n) per operation in the cell probe model. (C) 2004 Elsevier Inc. All rights reserved.
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Information and Computation
volume
193
issue
2
pages
75 - 83
publisher
Elsevier
external identifiers
  • wos:000223687300001
  • scopus:4243060465
ISSN
1090-2651
DOI
10.1016/j.ic.2004.04.006
language
English
LU publication?
yes
id
5e8dcf0d-6680-40fd-bdaf-94ba70355b03 (old id 267783)
date added to LUP
2007-09-03 16:03:18
date last changed
2017-01-01 04:24:50
@article{5e8dcf0d-6680-40fd-bdaf-94ba70355b03,
  abstract     = {We consider the problem of maintaining a string of n brackets '('or')' under the operation reverse(i) that changes the ith bracket from '('to')' or vice versa, and returns 'yes' if and only if the resulting string is properly balanced. We show that this problem can be solved on the RAM in time O(log n/log log n) per operation using linear space and preprocessing. Moreover, we show that this is optimal in the sense that every data structure supporting reverse (no matter its space and preprocessing complexity) needs time Omega(Iog n/log log n) per operation in the cell probe model. (C) 2004 Elsevier Inc. All rights reserved.},
  author       = {Alstrup, S and Husfeldt, Thore and Rauhe, T},
  issn         = {1090-2651},
  language     = {eng},
  number       = {2},
  pages        = {75--83},
  publisher    = {Elsevier},
  series       = {Information and Computation},
  title        = {Dynamic nested brackets},
  url          = {http://dx.doi.org/10.1016/j.ic.2004.04.006},
  volume       = {193},
  year         = {2004},
}