Exploring LogCFL using language theory[HBNI Th13]

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.