Constant Width Planar Computation Characterizes ACC0
Constant Width Planar Computation Characterizes ACC0
复制标题
ACC0 的恒定宽度平面计算特性
DOI：
--
复制
发表时间：
2004
影响因子：
0.5
通讯作者：
Kristoffer Arnsfelt Hansen
中科院分区：
文献类型：
--
作者：
Kristoffer Arnsfelt Hansen
摘要我们用一类自然的等宽电路，即等宽多项式尺寸平面电路，得到了ACC 0的一个特征。这是通过一类非循环有向图，它可以嵌入在这样一种方式，所有的弧流沿沿着相同方向的轴的圆柱表面的特征。
Abstract We obtain a characterization of ACC0 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.