Dynamic nested brackets
(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:
https://lup.lub.lu.se/record/267783
- author
- Alstrup, S ; Husfeldt, Thore LU and Rauhe, T
- organization
- publishing date
- 2004
- 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
- 2016-04-01 11:39:25
- date last changed
- 2022-01-26 08:16: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}}, doi = {{10.1016/j.ic.2004.04.006}}, volume = {{193}}, year = {{2004}}, }