ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > PUSHDOWN AUTOMATA:
Reports tagged with pushdown automata:
TR07-087 | 11th July 2007
Nutan Limaye, Meena Mahajan, B. V. Raghavendra Rao

Arithmetizing classes around NC^1 and L

The parallel complexity class NC^1 has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. \cite{CMTV} considered arithmetizations of two of these classes, #NC^1 and #BWBP. We further this study to include arithmetization of other classes. In particular, we show that counting paths ... more >>>



ISSN 1433-8092 | Imprint