Name
Abstract | ||
|---|---|---|
Following recent works connecting two-variable logic to circuits and monoids, we establish, for numerical predicate sets P satisfying a certain closure property, a one-to-one correspondence between F O(<; P)-uniform linear circuits, two-variable formulas with P predicates, and weak block products of monoids. In particular, we consider the case of linear TC0, ma- jority quantiers, and nitely typed monoids. This correspondence will hold for any numerical predicate set which is F O(<)-closed and whose predicates do not depend on the input length. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.tcs.2013.07.005 | Mathematical Foundations of Computer Science |
Keywords | Field | DocType |
numerical predicate set,logical characterization,linear circuit,two-variable logic,uniform linear threshold circuit,recent work,language recognition power,recent technique,certain closure property,threshold circuit | Discrete mathematics,Combinatorics,Closure (mathematics),Monoid,Predicate (grammar),Electronic circuit,Linear circuit,Mathematics | Journal |
Volume | ISSN | ISBN |
501, | 0304-3975 | 3-540-74455-X |
Citations | PageRank | References |
8 | 0.67 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Behle | 1 | 23 | 4.14 |
| Andreas Krebs | 2 | 17 | 2.86 |
| Mark Mercer | 3 | 8 | 0.67 |