Jain, A K
(2014)
Improved Streaming Algorithm for Dyck(s) Recognition.
Masters thesis, Indian Institute of Technology, Hyderabad.
Preview 

Text
Anubhav_Kumar_jain_cs11m04.pdf
 Submitted Version
Download (460kB)

Abstract
Keeping in mind, that any context free language can be mapped to a subset of Dyck languages and by seeing various
database applications of Dyck, mainly verifying the wellformedness of XML file, we study the randomized streaming
algorithms for the recognition of Dyck(s) languages, with s different types of parenthesis. The main motivation of this
work is well known space bound for any Tpass streaming algorithm is
(√n/T).
Let x be the input stream of length n with maximum height hmax. Here we present a singlepass randomized streaming
algorithms to decide the membership of x in Dyck(s) using Counting Bloomfilter (CBF) with space O (hmax) bits,
ploylog(n) time per letter with twosided error probability. Twosided error is because of the false negative and false
positives of counting bloomfilter. This algorithms denies the necessity of streaming reduction of Dyck(s) into Dyck(2),
that reduces the space even further by the factor of O (log s), compared to those uses streaming reduction.
We also present an improved singlepass randomized streaming algorithm for recognizing Dyck(2) with space O (√n)
bits, which is the proven lower bound. Time bound is same polylog(n), as other existing algorithms and error is onesided.
In this algorithm, we extended the existing approach of periodically compressing stack information. Existing approach
uses two stacks and a linear hash function, instead of this we are using three stacks and same linear hash function to
achieve space lower bound of O (√n).
We also present another singlepass streaming algorithm with O (hmax) space that uses counting bloomfilter and
directly acts on Dyck(s)
[error in script]
Actions (login required)

View Item 