Circuits on cylinders
Contribuinte(s) |
Lingas, A Nilsson, BJ |
---|---|
Data(s) |
2003
|
Resumo |
We consider the computational power of constant width polynomial size cylindrical circuits and non deterministic branching programs. We show that every function computed by a Pi(2) o MOD o AC(0) circuit can also be computed by a constant width polynomial size cylindrical nondeterministic branching program (or cylindrical circuit) and that every function computed by a constant width polynomial size cylindrical circuit belongs to ACC(0). |
Formato |
application/pdf |
Identificador |
http://eprints.iisc.ernet.in/39775/1/Circuits_on.pdf Hansen, Kristoffer Arnsfelt and Miltersen, Peter Bro and Vinay, V (2003) Circuits on cylinders. In: Lecture Notes in Computer Science, 2751 . pp. 171-182. |
Publicador |
Springer |
Relação |
http://www.springerlink.com/content/dwxm3wltjjjjmq1t/ http://eprints.iisc.ernet.in/39775/ |
Palavras-Chave | #Computer Science & Automation (Formerly, School of Automation) |
Tipo |
Editorials/Short Communications PeerReviewed |