Name
Abstract | ||
|---|---|---|
We extend the familiar program of understanding circuit complexity in terms of regular languages to visibly counter languages. Like the regular languages, the visibly counter languages are (mathrm {NC}^{1})- complete. We investigate what the visibly counter languages in certain constant depth circuit complexity classes are. We have initiated this in a previous work for (mathrm {AC}^{0}). We present characterizations and decidability results for various logics and circuit classes. In particular, our approach yields a way to understand (mathrm {TC}^{0}), where the regular approach fails. |
Year | Venue | DocType |
|---|---|---|
2015 | MFCS | Conference |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Hahn | 1 | 38 | 3.60 |
| Andreas Krebs | 2 | 3 | 4.15 |
| Klaus-Jörn Lange | 3 | 274 | 30.58 |
| Michael Ludwig | 4 | 3 | 1.80 |