Arithmetizing Classes Around NC 1 and L
作者： Nutan Limaye , Meena Mahajan , B. V. Raghavendra Rao
DOI: 10.1007/978-3-540-70918-3_41
关键词:
摘要: The parallel complexity class NC1 has many equivalent models such as bounded width branching programs. Caussinus et.al[10] considered arithmetizations of two these classes, #NC1 and #BWBP. We further this study to include arithmetization other classes. In particular, we show that counting paths in programs over visibly pushdown automata the same power #BWBP, while proof-trees logarithmic formulae #NC1. also consider polynomial-degree restrictions SCi, denoted sSCi, Boolean sSC1 lies between L, whereas sSC0 equals NC1. On hand, #sSC0 contains #BWBP is contained FL, #sSC1 SC2. investigate some closure properties newly defined arithmetic
springer.com
imsc.res.in 
iitb.ac.in 参考文章(36)
Kurt Mehlhorn, Pebbling mountain ranges and its application to DCFL-recognition international colloquium on automata, languages and programming. pp. 422- 435 ,(1980) , 10.1007/3-540-10003-2_89
Eric Allender, The Division Breakthroughs. Bulletin of The European Association for Theoretical Computer Science. ,vol. 74, pp. 61- 77 ,(2001)
Hervé Caussinus, Denis Thérien, Heribert Vollmer, Pierre McKenzie, Nondeterministic NC 1 Computation. Journal of Computer and System Sciences. ,vol. 57, pp. 200- 212 ,(1998)
Kurt Mehlhorn, Pebbling Moutain Ranges and its Application of DCFL-Recognition international colloquium on automata, languages and programming. pp. 422- 435 ,(1980)
Heribert Vollmer, Introduction to Circuit Complexity: A Uniform Approach ,(2010)
Markus Holzer, Klaus -Jörn Lange, On the Complexities of Linear LL(1) and LR(1) Grammars fundamentals of computation theory. pp. 299- 308 ,(1993) , 10.1007/3-540-57163-9_25
David S. JOHNSON, A catalog of complexity classes Handbook of theoretical computer science (vol. A). pp. 67- 161 ,(1991) , 10.1016/B978-0-444-88071-0.50007-2
H. Caussinus, P. McKenzie, D. Therien, H. Vollmer, Nondeterministic NC/sup 1/ computation conference on computational complexity. pp. 12- 21 ,(1996) , 10.1109/CCC.1996.507664
Nutan Limaye, Meena Mahajan, Antoine Meyer, On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata Computer Science – Theory and Applications. ,vol. 14, pp. 240- 251 ,(2008) , 10.1007/978-3-540-79709-8_25
K.-J. Lange, Complexity and structure in formal language theory structure in complexity theory annual conference. pp. 224- 238 ,(1993) , 10.1109/SCT.1993.336523