| dc.contributor.author |
Lagogiannis, G |
en |
| dc.date.accessioned |
2014-06-06T06:53:06Z |
|
| dc.date.available |
2014-06-06T06:53:06Z |
|
| dc.date.issued |
2014 |
en |
| dc.identifier.issn |
01290541 |
en |
| dc.identifier.uri |
http://dx.doi.org/10.1142/S0129054114500026 |
en |
| dc.identifier.uri |
http://62.217.125.90/xmlui/handle/123456789/6367 |
|
| dc.subject |
balanced parenthesis string |
en |
| dc.subject |
parent-queries |
en |
| dc.subject |
Union-split-find |
en |
| dc.title |
Parent queries over dynamic balanced parenthesis strings |
en |
| heal.type |
journalArticle |
en |
| heal.identifier.primary |
10.1142/S0129054114500026 |
en |
| heal.publicationDate |
2014 |
en |
| heal.abstract |
We maintain a balanced parenthesis string under insertions and deletions of parenthesis-pairs in such a way that we can efficiently answer parent queries, i.e., given a parenthesis-pair, we want to find the pair that immediately encloses it. Each parenthesis symbol is attached on a node, and we have n such nodes drawn on a straight line. We achieve O(logn/loglogn) worst-case time per operation on a Pointer Machine, matching the known lower bound on the problem. By transferring our solution to a RAM, we are able to achieve O(√logn/loglogn) worst case time per update, assuming that we know in advance that the parenthesis-pair to be inserted does not destroy the balance of the parenthesis string. © World Scientific Publishing Company. |
en |
| heal.publisher |
World Scientific Publishing Co. Pte Ltd |
en |
| heal.journalName |
International Journal of Foundations of Computer Science |
en |
| dc.identifier.issue |
1 |
en |
| dc.identifier.volume |
25 |
en |
| dc.identifier.doi |
10.1142/S0129054114500026 |
en |
| dc.identifier.spage |
25 |
en |
| dc.identifier.epage |
57 |
en |