Exploring LogCFL using language theory[HBNI Th 13]

DSpace/Manakin Repository

Exploring LogCFL using language theory[HBNI Th 13]

Show simple item record

dc.contributor.author Limaye, Nutan
dc.date.accessioned 2010-04-13T06:29:46Z
dc.date.available 2010-04-13T06:29:46Z
dc.date.issued 2010-04-13T06:29:46Z
dc.date.submitted 2009
dc.identifier.uri http://hdl.handle.net/123456789/175
dc.description.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. en_US
dc.publisher.publisher
dc.subject Language Theory en_US
dc.subject HBNI Th 13 en_US
dc.title Exploring LogCFL using language theory[HBNI Th 13] en_US
dc.type.degree Ph.D en_US
dc.type.institution HBNI en_US
dc.description.advisor Meena Mahajan
dc.description.pages 108p. en_US
dc.type.mainsub Computer Science en_US

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 simple item record

Search DSpace


Advanced Search

Browse

My Account