A Logical Characterization of Constant-Depth Circuits over the Reals
A Logical Characterization of Constant-Depth Circuits over the Reals
复制标题
实数恒定深度电路的逻辑表征
DOI：
10.1007/978-3-030-88853-4_2
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
H. Vollmer
中科院分区：
文献类型：
--
作者：
T. Barlag;H. Vollmer
在本文中，我们给出了实值计算的伊默曼定理，即我们定义了在实数上运行的无界扇入电路，并表明多项式大小和恒定深度的此类电路族准确地决定了可以在 Cucker 和 Meer 意义上的一阶逻辑结构中定义的实数向量集。我们的表征既适用于非均匀性，也适用于许多自然均匀性 状况。
In this paper we give an Immerman Theorem for real-valued computation, i.e., we define circuits of unbounded fan-in operating over real numbers and show that families of such circuits of polynomial size and constant depth decide exactly those sets of vectors of reals that can be defined in first-order logic on-structures in the sense of Cucker and Meer.Our characterization holds both non-uniformly as well as for many natural uniformity conditions.
登录
查看更多内容
DOI：
--
发表时间：
1995
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
E. Grädel;K. Meer
通讯作者：
K. Meer
影响因子：
1.6
作者：
IMMERMAN, N
通讯作者：
IMMERMAN, N
DOI：
--
发表时间：
1988
期刊：
[Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
L. Blum;M. Shub;S. Smale
通讯作者：
S. Smale
Pr != Ncr
影响因子：
1.7
作者：
F. Cucker
通讯作者：
F. Cucker
DOI：
10.1016/j.apal.2019.04.006
发表时间：
2019
期刊：
Ann. Pure Appl. Log.
影响因子：
--
作者：
A. Haak;H. Vollmer
通讯作者：
H. Vollmer