Aspects of 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.