ALCOMFT-TR-03-194

Kristoffer Arnsfelt Hansen
Constant width planar computation characterizes ACC⁰
Århus. Work package 4. December 2003.

Abstract: We obtain a characterization of ACC^0 in terms of a natural class of constant width circuits, namely in terms of constant width polynomial size planar circuits. This is shown via a characterization of the class of acyclic digraphs which can be embedded on a cylinder surface in such a way that all arcs flow along the same direction of the axis of the cylinder.

Postscript file: ALCOMFT-TR-03-194.ps.gz (160 kb).