On Symmetric Circuits and Fixed-Point Logics
On Symmetric Circuits and Fixed-Point Logics
复制标题
对称电路和定点逻辑
DOI：
10.1007/s00224-016-9692-2
复制
发表时间：
2016
影响因子：
0.5
通讯作者：
Anderson M
中科院分区：
文献类型：
--
作者：
Anderson M
我们研究的关系结构，如图，这是由家庭的布尔电路决定的属性。决定这些性质的电路必须对输入结构的元素的排列保持不变。我们专注于家庭的电路是对称的，即，其不变性由输入结构排列引起的电路自同构证明的电路。我们表明，这种家庭的表达能力是密切相关的逻辑中的可定义性。特别是，我们表明，结构上定义的查询由统一的家庭的对称布尔电路与多数门正是那些可定义的不动点逻辑计数。这表明，不可表达的结果，在后者的逻辑导致对多项式大小的家庭的对称电路的下限。
We study properties of relational structures, such as graphs, that are decided by families of Boolean circuits. Circuits that decide such properties are necessarily invariant to permutations of the elements of the input structures. We focus on families of circuits that are symmetric, i.e., circuits whose invariance is witnessed by automorphisms of the circuit induced by the permutation of the input structure. We show that the expressive power of such families is closely tied to definability in logic. In particular, we show that the queries defined on structures by uniform families of symmetric Boolean circuits with majority gates are exactly those definable in fixed-point logic with counting. This shows that inexpressibility results in the latter logic lead to lower bounds against polynomial-size families of symmetric circuits.
登录
查看更多内容
带计数的定点逻辑中的最大匹配和线性规划
DOI：
10.1109/lics.2013.23
发表时间：
2013
期刊：
--
影响因子：
--
作者：
Anderson M
通讯作者：
Anderson M
有界变量逻辑和计数：有限模型研究
DOI：
--
发表时间：
1997
期刊：
Lecture Notes in Logic
影响因子：
--
作者：
M. Otto
通讯作者：
M. Otto
无选择多项式时间
影响因子：
0.8
作者：
A. Blass;Y. Gurevich;S. Shelah
通讯作者：
S. Shelah
无选择多项式时间、计数和 Cai-Fürer-Immerman 图：（扩展摘要）
DOI：
10.1016/j.apal.2007.11.011
发表时间：
2008
期刊：
Ann. Pure Appl. Log.
影响因子：
--
作者：
A. Dawar;David Richerby;Benjamin Rossman
通讯作者：
Benjamin Rossman
有界变量逻辑和计数
DOI：
10.1007/978-3-662-21676-7
发表时间：
1997
期刊：
Electron. J. Comb.
影响因子：
--
作者：
M. Otto
通讯作者：
M. Otto