Sentences and Circuits
Sentences and Circuits
批准号:
8805880
负责人:
James Lynch
金额:
$5.15万
依托单位:
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
1988
资助国家:
美国
项目状态:
已结题
起止时间:
1988-07-15 至 1990-12-31
中文摘要
点击翻译按钮获取中文摘要
英文摘要
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.
期刊论文(0)
专著(0)
科研奖励(0)
会议论文
Workshop on Logic and Systems Biology
-
批准号:1430556
-
项目类别:Standard Grant
-
资助金额:$1.0万
-
财政年份:2014
-
负责人:James Lynch
-
依托单位:
Workshop on Logic and Systems Biology
-
批准号:1231446
-
项目类别:Standard Grant
-
资助金额:$0.8万
-
财政年份:2012
-
负责人:James Lynch
-
依托单位:
Collaborative Research for Developing ATD: Bayesian Methods in Syndromic Surveillance: CAR Models and Computational Implementation
-
批准号:0914921
-
项目类别:Standard Grant
-
资助金额:$2.76万
-
财政年份:2009
-
负责人:James Lynch
-
依托单位:
Dynamic Models and Decision Making for Complex Reliability Systems
-
批准号:0805809
-
项目类别:Continuing Grant
-
资助金额:$25.0万
-
财政年份:2008
-
负责人:James Lynch
-
依托单位:
The Workshop on Logic and Systems Biology
-
批准号:0629553
-
项目类别:Standard Grant
-
资助金额:$0.5万
-
财政年份:2006
-
负责人:James Lynch
-
依托单位:
Stochastic Models and Inference for the Reliability of Complex Systems
-
批准号:0243594
-
项目类别:Continuing Grant
-
资助金额:$22.43万
-
财政年份:2003
-
负责人:James Lynch
-
依托单位:
Schools as Precipitants of Crime: The Routine Activities and the Sociology of Place
-
批准号:0071124
-
项目类别:Standard Grant
-
资助金额:$0.41万
-
财政年份:2000
-
负责人:James Lynch
-
依托单位:
Random Finite Structures
-
批准号:9406809
-
项目类别:Standard Grant
-
资助金额:$8.81万
-
财政年份:1994
-
负责人:James Lynch
-
依托单位:
Collaborative Research on the Use of Case-Control Methods to Test Opportunity Theory
-
批准号:9115171
-
项目类别:Standard Grant
-
资助金额:$2.53万
-
财政年份:1991
-
负责人:James Lynch
-
依托单位:
Problems in Finite Model Theory
-
批准号:9006303
-
项目类别:Continuing Grant
-
资助金额:$8.03万
-
财政年份:1990
-
负责人:James Lynch
-
依托单位:
Problems in Finite Model Theory
-
批准号:8605551
-
项目类别:Standard Grant
-
资助金额:$3.76万
-
财政年份:1986
-
负责人:James Lynch
-
依托单位:
Mathematical Sciences: NSF-CBMS Regional Conference on the Construction and Salient Properties of Nonparametric Priors;University Park, PA; June 3-7, 1985
-
批准号:8503702
-
项目类别:Standard Grant
-
资助金额:$2.5万
-
财政年份:1985
-
负责人:James Lynch
-
依托单位:
Problems in Finite Model Theory (Computer Research)
-
批准号:8402206
-
项目类别:Continuing Grant
-
资助金额:$3.8万
-
财政年份:1984
-
负责人:James Lynch
-
依托单位:
Problems in Finite Model Theory
-
批准号:8002695
-
项目类别:Standard Grant
-
资助金额:$4.92万
-
财政年份:1980
-
负责人:James Lynch
-
依托单位:
Reliability Distributions: Representations in Terms of Extreme Points
-
批准号:7904698
-
项目类别:Standard Grant
-
资助金额:$0.74万
-
财政年份:1979
-
负责人:James Lynch
-
依托单位:
Solution Sets to Combinatorial Problems
-
批准号:7801832
-
项目类别:Standard Grant
-
资助金额:$0.71万
-
财政年份:1978
-
负责人:James Lynch
-
依托单位:
海外基金