Aspects of Computation Theory

计算理论方面

• 批准号: 9108631
• 负责人: Phokion Kolaitis
• 金额: $ 11.8万
• 依托单位: University of California-Santa Cruz
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-07-01 至 1994-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9108631&HistoricalAwards=false
• 关键词: Aspects; Computation; Theory

This project will contribute to the application of logic to computer science, specifically complexity theory, database theory, and asymptotic combinatorics. The project has three parts. The first part is a systematic investigation of algorithmic problems about paths in graphs from the viewpoint of logical expressibility. Important path problems will be classified according to their expressibility in the DATALOG query language or in extensions of DATALOG with negation. The second part is an exploration of connections between fixpoint logic and computational complexity. In addition, a structural theory of optimization will be developed according to the logical definability of optimization problems. The third part is a study of asymptotic probabilities on finite structures, such as zero-one laws and associated decision problems for extensions of first-order logic under variable probability measures.

这个项目将有助于逻辑在计算机中的应用 科学，特别是复杂性理论，数据库理论， 渐近组合学 该项目有三个部分。 第一 第一部分是对路径问题的算法研究 从逻辑可表达性的角度来看。 重要 路径问题将根据它们的可表达性进行分类， DATALOG查询语言或带有否定的DATALOG扩展。 第二部分是对不动点之间联系的探讨 逻辑和计算复杂性。 此外，结构理论 将根据逻辑开发优化 优化问题的可定义性。 第三部分是对中国传统文化的研究。 有限结构上的渐近概率，如零-一定律 一阶逻辑扩展的相关判定问题 在可变概率测度下。