Dynamic Nested Brackets

Stephen Alstrup, Theis Rauhe, Thore Husfeldt

Publikation: Bog / Antologi / Rapport / Ph.D.-afhandlingRapportForskning

Abstract

We consider the problem of maintaining a string of brackets like (()(()))of length n under a single operation reverse(i). The operation reverse(i)  changes the the letter from '(' to) ` ' or vice versa, and returns `yes' if and only if the updated string is balanced.
We give lower and upper bounds showing that the complexity of reverse(i) is (-)(log n/loglog n).
OriginalsprogEngelsk
UdgivelsesstedCopenhagen
ForlagIT-Universitetet i København
UdgaveTR-2001-9
Antal sider8
ISBN (Elektronisk)87-7949-012-3
StatusUdgivet - nov. 2001
Udgivet eksterntJa
NavnIT University Technical Report Series
NummerTR-2001-9
ISSN1600-6100

Fingeraftryk

Dyk ned i forskningsemnerne om 'Dynamic Nested Brackets'. Sammen danner de et unikt fingeraftryk.

Citationsformater