Name
Abstract | ||
|---|---|---|
Motivated by the open question whether $\mbox{TC{$^0$}}=\mbox{NC{$^1$}}$ we consider the case of linear size TC0. We use the connections between circuits, logic, and algebra, in particular the characterization of $\mbox{TC{$^0$}}$ in terms of finitely typed monoids. Applying algebraic methods we show that the word problem for finite non-solvable groups cannot be described by a FO+MOD+MAJ[REG] formula using only two variables. This implies a separation result of FO[REG]-uniform linear TC0 from linear NC1. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-00982-2_11 | LATA |
Keywords | Field | DocType |
word problem,algebraic method,finite non-solvable group,open question,non-solvable groups,linear nc1,separation result,linear size tc0,solvable group | Discrete mathematics,Combinatorics,Mod,Algebraic number,Word problem (mathematics education),Monoid,Solvable group,Regular language,Mathematics | Conference |
Volume | ISSN | Citations |
5457 | 0302-9743 | 3 |
PageRank | References | Authors |
0.42 | 10 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Behle | 1 | 23 | 4.14 |
| Andreas Krebs | 2 | 27 | 5.83 |
| Stephanie Reifferscheid | 3 | 17 | 2.27 |