A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits
A Model-Theoretic Characterization of Constant-Depth Arithmetic Circuits
复制标题
恒定深度算术电路的模型理论表征
DOI：
10.1016/j.apal.2019.04.006
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
H. Vollmer
中科院分区：
文献类型：
--
作者：
A. Haak;H. Vollmer
我们研究了由无界加法和乘法门的恒定深度多项式大小的算术电路计算的函数的#AC0类。到目前为止，还没有已知的算术电路类的模型理论表征。受Immerman对布尔电路类AC0刻画的启发，我们纠正了这种情况，并发展了#AC0的刻画。我们的刻画可以解释为：#AC0中的函数正是计算一阶模型检验对策中获胜策略的函数。我们的结果的一个结果是TC0的一个新的模型论刻画，TC0是被恒定深度多项式大小的多数电路接受的语言类。
We study the class# AC 0 of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fan-in addition and multiplication gates. No model-theoretic characterization for arithmetic circuit classes is known so far. Inspired by Immerman's characterization of the Boolean circuit class AC 0, we remedy this situation and develop such a characterization of# AC 0. Our characterization can be interpreted as follows: Functions in# AC 0 are exactly those functions counting winning strategies in first-order model checking games. A consequence of our results is a new model-theoretic characterization of TC 0, the class of languages accepted by constant-depth polynomial-size majority circuits.
登录
查看更多内容
具有负常数的 AC0 电路计数
DOI：
--
发表时间：
1998
期刊：
International Symposium on Mathematical Foundations of Computer Science
影响因子：
--
作者：
A. Ambainis;D. M. Barrington;H. LeThanh
通讯作者：
H. LeThanh
DOI：
10.1016/j.jcss.2020.04.002
发表时间：
2021
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
A. Durand;A. Haak;J. Kontinen;H. Vollmer
通讯作者：
H. Vollmer
细胞运动和出租车的随机模型
影响因子：
1.9
作者：
E. Ionides;Kathy S. Fang;R. Rivkah Isseroff;George Oster
通讯作者：
George Oster
具有计数功能的定点逻辑的本质和强大功能
DOI：
--
发表时间：
2015
期刊：
影响因子：
--
作者：
N. Immerman
通讯作者：
N. Immerman
DOI：
10.1006/jcss.1995.1039
发表时间：
1995
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
Sanjeev Saluja;K. Subrahmanyam;Madhukar N. Thakur
通讯作者：
Madhukar N. Thakur