Aspects of Computation Theory

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

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.