Aspects of Computation Theory

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

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.