Constant Width Planar Computation Characterizes ACC0

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • Department of Computer Science

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.

Original languageEnglish
Title of host publicationSTACS 2004 : 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004. Proceedings
EditorsVolker Diekert, Michel Habib
Number of pages12
PublisherSpringer
Publication year2004
Pages44-55
DOIs
Publication statusPublished - 2004
Event21st Annual Symposium on Theoretical Aspects of Computer Science  (STACS 2004) - Montpellier, France
Duration: 25 Mar 200727 Mar 2007

Conference

Conference21st Annual Symposium on Theoretical Aspects of Computer Science  (STACS 2004)
LandFrance
ByMontpellier
Periode25/03/200727/03/2007
SeriesLecture Notes in Computer Science
Volume2996

See relations at Aarhus University Citationformats

ID: 281981