Exploring LogCFL using language theory[HBNI Th 13]

DSpace/Manakin Repository

Exploring LogCFL using language theory[HBNI Th 13]

Show full item record

Title: Exploring LogCFL using language theory[HBNI Th 13]
Author: Limaye, Nutan
Advisor: Meena Mahajan
Degree: Ph.D
Main Subjects: Computer Science
Institution: HBNI
Year: 2009
Pages: 108p.
Abstract: The Complexity classes contained in LogCFL is explored in this thesis by drawing connections to Language theory. Many depth reduction techniques involved in this process are studied along the way. The two factor-2 approximation algorithms are considered for BLOCK SORTING and it is shown that both the algorithms could be implemented in LogCFL. The depth reduction techniques used here are specialized for these problems and explicit NC^2 algorithms are given. The membership problem is studied for multi-pushdown machines. The stack in these machines are ordered and pop moves are allowed on the first non-empty stack. It is proved that the membership problem for these machines is complete for logCFL. Visibly pushdown languages(VPLs) and many generalizations of VPLs are considered and these languages are used to draw connections to the complexity classes inside LogCFL. It is proved that the height of the stack for these machines are functions computable in NC^1, L, and LogCFL, respectively, and proved that the membership problem for all three of them is in L^h where h is the complexity of the height function. Also multi stack pushdown machines are considered with visible stacks. The membership problem for multi-stack pushdown is considered with bounded phases and show LogCFL upper bound. The counting problem for VPLs, and its generalizations, namely, rhPDA)FST), rhPDA(rDPDA(1-turn)), and rhPDA(PDT) are considered, and proving for all LogDCFL upperbound. The counting functions corresponding to VPLs are analyzed for their closure properties.
URI: http://hdl.handle.net/123456789/175

Files in this item

Files Size Format View
HBNITH 13.pdf 848.3Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record

Search DSpace


Advanced Search

Browse

My Account