Name
Abstract | ||
|---|---|---|
Low circuit complexity classes and regular languages exhibit very tight interactions that shade light on their respective expressiveness. We propose to study these interactions at a functional level, by investigating the deterministic rational transductions computable by constant-depth, polysize circuits. To this end, a circuit framework of independent interest that allows variable output length is introduced. Relying on it, there is a general characterization of the set of transductions realizable by circuits. It is then decidable whether a transduction is definable in AC(0) and, assuming a well-established conjecture, the same for ACC(0). |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-662-48057-1_11 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Circuit complexity,Computer science,Decidability,Regular language,Electronic circuit,Conjecture,Expressivity | Conference | 9234 |
ISSN | Citations | PageRank |
0302-9743 | 3 | 0.45 |
References | Authors | |
12 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michaël Cadilhac | 1 | 15 | 7.61 |
| Andreas Krebs | 2 | 27 | 5.83 |
| Michael Ludwig | 3 | 3 | 1.80 |
| Charles Paperman | 4 | 9 | 5.00 |