Aspects of Computation Theory

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

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.