Sentences and Circuits

点击翻译按钮获取中文摘要

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.