Sentences and Circuits

本文将研究有限模型上句子的表达能力和无限扇入电路的计算能力。将考虑两种电路的深度和大小的下界：门是and， or和NOT的，门是阈值函数的。此外，还将研究一些阈值电路学习算法的有效性。另一个主题是受随机更新影响的关系数据库的平均行为。首席研究员最近的结果表明，在某些情况下，随着数据库的发展，查询的真值接近一个与数据库的初始配置无关的限制值。建议的研究是将这些结果扩展到更一般的情况。计划在有限模型理论方面的工作。一个课题是利用模型理论约简得到非线性时间下界。二是分析句子概率在某一类有限模型上的渐近行为。

The expressive power of sentences on finite models and the computational power of circuits with unbounded fan-in will be studied. Lower bounds on the depth and size of two kinds of circuits will be considered: those whose gates are AND, or, and NOT, and those whose gates are threshold functions. In addition, the effectiveness of some learning algorithms for threshold circuits will be investigated. Another topic is the average behavior of relational data bases that are subjected to random updates. Recent results of the principal investigator show that, in certain cases, as the data base evolves, the truth of a query approaches a limiting value independent of the initial configuration of the data base. The proposed research is to extend these results to more general cases. Work in finite model theory is planned. One topic is to obtain nonlinear time lower bounds using model-theoretic reductions. The other is to analyze the asymptotic behavior of the probability of sentences over certain classes of finite models.