Thore Husfeldt

News

New paper with Alstrup and Rauhe

“Dynamic nested brackets,” to appear in Information and Computation.

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/loglog 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 Ω(log n/loglog n) per operation in the cell probe model.

Full paper under On-line papers.

As a related curiosity, note this Perl regex:

/^(?{local$d=0})(?:\((?{$d++})|\)(?{$d—-})(?(?{$d<0})(?!))|(?>[^()]*))*(?(?{$d!=0})(?!))$/

Mon, 12 Jan 2004 | Category: News | Permanent link