Aspects of Computation Theory

计算理论方面

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

This work investigates a broad spectrum of problems dealing with logic in computer science that span finite model theory, database theory, complexity theory, and optimization theory. The question of whether or not certain important algorithmic problems are expressible in various logical query languages, such as Datalog and extensions of Datalog with negation, are examined. Further, the relationship between first- order logic, fixpoint logic, and polynomial-time computability on arbitrary classes of finite structures are explored. In the area of logical definability and asymptotic probabilities, 0-1 laws are investigated for certain powerful extensions of fixpoint logic and an attempt is made to find necessary and sufficient conditions for the existence of 0-1 laws under variable probability measures. In a different line of investigation, the descriptive complexity of optimization problems continues to be developed. An attempt is made to determine if there is an effective syntax for the approximable NP optimization problems and to seek structural explanations for the diverse behavior of polynomial-time optimization problems with respect to parallel approximation.

这项工作调查了广泛的问题处理逻辑在计算机科学中，跨越有限模型理论，数据库理论，复杂性理论和优化理论。 某些重要的算法问题是否可以用各种逻辑查询语言来表达，如Datasheet和Datasheet的否定扩展，进行了研究。此外，一阶逻辑，不动点逻辑和多项式时间的可计算性之间的关系，对任意类的有限结构进行了探讨。 在逻辑可定义性和渐近概率领域，研究了不动点逻辑的某些强有力的扩展的0-1律，并试图找到必要的和 变量下0-1律存在的充分条件 概率测度 在另一项调查中， 优化问题的描述复杂性继续发展。 进行尝试 以确定是否存在有效的语法， 近似的NP优化问题，并寻求结构解释的不同行为的多项式时间优化问题的并行逼近。