Improved Streaming Algorithm for Dyck(s) Recognition

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 well-formedness 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 T-pass streaming algorithm is (√n/T). Let x be the input stream of length n with maximum height hmax. Here we present a single-pass 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 two-sided error probability. Two-sided 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 single-pass 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 one-sided. 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 single-pass streaming algorithm with O (hmax) space that uses counting bloomfilter and directly acts on Dyck(s)

[error in script]

IITH Creators: